2019牛客暑期多校(第五场) 写题记录

A digits 2

A题找到数字连续出现同时是它倍数的 n 《100 输出长度也小于100*100
//水

#include <bits/stdc++.h>
using namespace std;

int main(){
	int n, m;
	cin >> n;
	for(int i = 1; i <= n; i++) {
		cin >> m;
		int ans =0;
		for(int j = 1; j <= m; j ++) {
			cout << m ;
		}cout << endl;
	}
    return 0;
}

B generator 1

B题欧拉降幂死的体无全尸
我们每一位考虑最后一位开始向前
每放入这个数将之前的矩阵 ^ 10
就如同正常的整数几次方我们分开乘了
111 = （（（1 * 10 ） + 1 ）* 10 ）+ 1；

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define int long long
int mod ;

struct MAT{
	int a[5][5];
	MAT (){
		memset(a, 0, sizeof a);
	}
	void init() {
		for(int i = 1; i <= 2; i ++) a[i][i] = 1;
	}
	
	friend MAT operator * (const MAT &a, const MAT &b) {
		MAT c;
		c.a[1][1] = c.a[2][2] = c.a[1][2] = c.a[2][1] = 0;
		for(int i = 1; i <= 2; i ++) for(int k = 1; k <= 2; k ++) for(int j = 1; j <= 2; j ++)
			c.a[i][j] = (1ll * c.a[i][j] + 1ll * a.a[i][k] * b.a[k][j]) % mod;
		return c;
	}
	
	friend MAT operator ^ (MAT a, long long y) {
		MAT c;
		c.init();
		for(; y; y >>= 1) {
			if(y & 1) c = c * a;
			a = a * a;
		}
		return c;
	} 
};

signed main() {
	int x0, x1, a, b;
	string s;
	cin >> x0 >> x1 >> a >> b >> s >> mod;
	MAT A; A.a[1][1] = a, A.a[1][2] = b, A.a[2][1] = 1, A.a[2][2] = 0;
	MAT B; B.a[1][1] = x1, B.a[1][2] = 0, B.a[2][1] = x0, A.a[2][2] = 0;
	for(int i = s.size() - 1; i >= 0; i --) {
		if(s[i] - '0') {
			MAT t = (A ^ (signed(s[i] - '0')));
			B = t * B;
		}
		A = (A ^ 10);
	}
	cout << B.a[2][1] << endl;
	return 0;
}

F maximum clique 1

我们要将一堆数字分开找到集合里数字二进制1个数相差 >= 2 最多的集合输出

我们考虑二分图左边是1 个数奇数右边偶数
这样建图我们在同一侧的不管肿摸组合他们都可以
找到 < 2 之间的数字连边跑最大流
这样我们二分图匹配就能把这些找到不要的情况
原图减去这些就是最大独立集合

至于输出我们要考虑最后一次BFS depth数组如果s能到达就意味着这个点并没有被和 t点一块割去
两边同侧而且与之自己相连同边的汇点 or 源点就是最大独立及

#include <bits/stdc++.h>
using namespace std;
const int maxn = 2e5 + 5;
const int N = 1e4 + 5;
const int INF = 0x3f3f3f3f;
int a[maxn], b[maxn];
int n, m;
int head[N], depth[N], cur[N], cnt, s, t;
int to[maxn << 2], nxt[maxn << 2], cap[maxn << 2];

int resbit(int i) {
    int res = 0;
    while(i) res ++, i -= (i & -i);
    return res;
}

bool chk(int i, int j) {
    int res = 0;
    int k = i ^ j;
    while(k) res++, k-=(k & -k);
    return res < 2;
}

void ade(int a, int b, int c) {
	to[++cnt] = b, cap[cnt] = c;
	nxt[cnt] = head[a], head[a] = cnt;
}

bool bfs(){
	queue<int> que;
	que.push(s);
	memset(depth, 0, sizeof(depth));
	depth[s] = 1;
	while(!que.empty()) {
		int u = que.front(); que.pop();
		for(int i = head[u]; i != -1; i = nxt[i]) {
			if(cap[i] > 0 && depth[to[i]] == 0) {
				depth[to[i]] = depth[u] + 1;
				que.push(to[i]);
			}
		}
	}
// for(int i = 0; i <= n + 1; i ++) {
// cout << i << " " <<depth[i] << endl;
// }
	if(depth[t]) return 1;
	else return 0;
}


int dfs(int u, int dist) {
	if(u == t) return dist;
	for(int &i = cur[u]; i != -1; i = nxt[i]) {
		if(depth[to[i]] == depth[u] + 1 && cap[i]) {
			int tmp = dfs(to[i], min(dist, cap[i]));
			if(tmp > 0) {
				cap[i] -= tmp;
				cap[i ^ 1] += tmp;
				return tmp;
			}
		}
	}
	return 0;
}

int dinic() {
	int res = 0, d;
	while(bfs()) {
		for(int i = 0; i < n + 5; i ++) cur[i] = head[i];
		while(d = dfs(s, INF)) res += d;
	}
	return res;
}

int main() {
    scanf("%d", &n);
    cnt = -1;
    memset(head, -1, (n + 5) * sizeof(int));
    for(int i = 1; i <= n; i ++) scanf("%d", a + i), b[i] = resbit(a[i]);

    s = 0, t = n + 1;
    for(int i = 1; i <= n; i ++) {
        if(b[i] % 2 == 1) ade(s, i, 1), ade(i, s, 0);
        else ade(i, t, 1), ade(t, i, 0);

        for(int j = i + 1; j <= n; j ++) {
            if(i == j) continue;
            if(chk(a[i], a[j])){
                if(b[i] % 2 == 1) ade(i, j, 1), ade(j, i, 0);
                else ade(j, i, 1), ade(i, j, 0);
            }
        }
    }
    int ans = dinic();

// for(int i = 0; i <= n + 1; i ++) {
// cout << i << " " <<depth[i] << endl;
// }
    int f = 0;
    printf("%d\n", n - ans);
    for(int i = 1; i <= n; i ++) {
        if((b[i] % 2 == 1) ^ (depth[i] == 0)){
            if(f) cout << " ";
            cout << a[i];
            f = 1;
        }
    }cout << endl;

    return 0;
}

G subsequence 1

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 3e3 + 5;
const int mod = 998244353;
int n, m, cas;
int dp[maxn][maxn];
int f[maxn][maxn];

char s[maxn], t[maxn];

void init() {
	f[0][0] = f[1][0] = f[1][1] = 1;
	for(int i = 2; i <= 3000; i ++) {
		f[i][0] = 1;
		for(int j = 1; j <= i; j ++)
			f[i][j] = (f[i - 1][j] + f[i - 1][j - 1]) %mod;
	}
}

int main() {
	init();
	cin >> cas;
	while(cas --) {
		cin >> n >> m;
		cin >> (s + 1) >> (t + 1);
		int ans = 0;
		for(int i = 0; i <= n; i ++) dp[i][0] = 1;

		for(int i = 1; i <= n; i++)
			for(int j = 1; j <= min(m, i); j++) {
				dp[i][j] = dp[i - 1][j];
				if(s[i] == t[j]) dp[i][j] = (1ll * dp[i][j] + dp[i - 1][j - 1]) % mod;
				if(s[i] > t[j] ) {
					ans = (1ll * ans + (ll)dp[i - 1][j - 1] * f[n - i][m - j]) % mod;
				}
			}
		for(int i = 1; i <= n; i ++) {
			if(s[i] == '0') continue;
			for(int j = m; j <= n - i; j ++)
				ans = (1ll * ans + f[n - i][j]) % mod;
 		}
 		cout << ans << endl;
	}
	return 0;
}

subsequence 2

这题是拓扑 orz
字符编号，这里每一个字符都保存一下他的位数和相对添加进来的位置就好了，
拓扑排序建边的时候建立相邻的边就好了，如果能建就是有解的

#include <bits/stdc++.h>
#define fastio ios::sync_with_stdio(false);cin.tie(0);
using namespace std;
typedef long long ll;
//#define int long long
const int maxn = 3e5 + 5;

int n, m, M;
int head[maxn], nums[30], deg[maxn], cnt;// 1e4 * 26 + 1e4 顶点极限
int to[maxn << 1], nxt[maxn << 1];

int getid(char s, int num) {
    return (s - 'a')*10000 + num;
}

int reid(int id) {
    return id / 10000 + 'a';
}

void ade(int a, int b) {
    to[++ cnt] = b;
    nxt[cnt] = head[a], head[a] = cnt;
}
string ans;
bool topsort() {
    ans = "";
    queue<int> que;
    for(int i = 0; i < 26; i ++) if(deg[i * 10000 + 1] == 0 && nums[i]) que.push(i * 10000 + 1);
    while(!que.empty()) {
        int x = que.front(); que.pop();
        ans.push_back(reid(x));
        for(int i = head[x]; i; i = nxt[i]) {
            int y = to[i];
            if(-- deg[y] == 0) que.push(y);
        }
    }
    return ans.size() == n;
}

signed main() {
	fastio;
	cin >> n >> m;
	M = (m - 1) * m / 2;
	string s1, s2;
	bool flag = 0;
	for(int i = 1, len; i <= M; i ++) {
        cin >> s1 >> len;
        if(len != 0) cin >> s2;
        if(flag) continue;
        int n0 = 0, n1 = 0, pre = -1, tmp;
        for(int j = 0; j < len; j ++) {
            tmp = 0;
            nums[s2[j] - 'a'] = 1;
            if(s2[j] == s1[0]) n0 ++,tmp = getid(s2[j], n0);
            else n1 ++,tmp = getid(s2[j], n1);
            if(pre != -1) {
                deg[tmp] ++;
                ade(pre, tmp);
            }
            pre = tmp;
        }
	}
	if(topsort()) cout << ans << endl;
	else cout << -1 << endl;
	return 0;
}