Codechef October Challenge 2019 Div.2

~~CodeChef = ccf~~

S10E

水题，直接模拟即可

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#define LL long long
using namespace std;
LL read() {
	LL k = 0, f = 1; char c = getchar();
	while(c < '0' || c > '9') {
		if(c == '-') f = -1;
		c = getchar();	
	}
	while(c >= '0' && c <= '9')
		k = k * 10 + c - 48, c = getchar();
	return k * f;
}
int a[100010];
int main() {
    int t = read();
    while(t--) {
        int n = read(), ans = 0;
        for(int i = 1; i <= n; ++i) {
            a[i] = read();
            int minn = 2147483647;
            for(int j = max(i-5, 1); j <= i-1; ++j)
                minn = min(minn, a[j]);
            if(minn > a[i]) ++ans;
        }
        printf("%d
", ans);
    }

    return 0;
}

SAKTAN

行和列分开处理，因为奇数+偶数=奇数，所以分别求出加了偶数次的行(ea)和列(eb)，加了奇数次的行(oa)和列(ob)最后答案就是(oa imes eb + ea imes ob)

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#define LL long long
using namespace std;
LL read() {
	LL k = 0, f = 1; char c = getchar();
	while(c < '0' || c > '9') {
		if(c == '-') f = -1;
		c = getchar();	
	}
	while(c >= '0' && c <= '9')
		k = k * 10 + c - 48, c = getchar();
	return k * f;
}
int a[100010], b[100010];
int main() {
    int t = read();
    while(t--) {
        memset(a, 0, sizeof(a));
        memset(b, 0, sizeof(b));
        int n = read(), m = read(), q = read();
        for(int i = 1; i <= q; ++i) {
            int x = read(), y = read();
            ++a[x], ++b[y];
        }
        LL oa = 0, ob = 0, ea = 0, eb = 0;
        for(int i = 1; i <= n; ++i)
            if(a[i] & 1) ++oa;
            else ++ea;
        for(int i = 1; i <= m; ++i)
            if(b[i] & 1) ++ob;
            else ++eb;
        LL ans = ob * ea + oa * eb;
        printf("%lld
", ans);
    }

    return 0;
}

MARM

每(3n)次操作是一个循环。但如果(n)是奇数，需特判最中间的数，当(k geq (n+1)/2)时，最中间的数恒为(0)
不要忘记开long long！

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#define LL long long
using namespace std;
LL read() {
	LL k = 0, f = 1; char c = getchar();
	while(c < '0' || c > '9') {
		if(c == '-') f = -1;
		c = getchar();
	}
	while(c >= '0' && c <= '9')
		k = k * 10 + c - 48, c = getchar();
	return k * f;
}
LL a[10010];
int main() {
    int t = read();
    while(t--) {
        LL n = read(), k = read();
        for(int i = 0; i < n; ++i) a[i] = read();

        LL flag = 0;
        if(k >= n/2ll+1ll) flag = 1;
        k = k % (3ll * n);
        
        for(LL i = 0; i <= k-1; ++i)
            a[i%n] ^= a[n-(i%n)-1ll];

        for(LL i = 0; i < n; ++i) {
            if((n & 1ll) && (i == n/2ll) && flag)
                printf("0 ");
            else printf("%lld ", a[i]);
        }
        printf("
");
    }

    return 0;
}

MSV

对每个数暴力分解因数，然后用桶记录每个因数出现了几次

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#define LL long long
using namespace std;
LL read() {
	LL k = 0, f = 1; char c = getchar();
	while(c < '0' || c > '9') {
		if(c == '-') f = -1;
		c = getchar();
	}
	while(c >= '0' && c <= '9')
		k = k * 10 + c - 48, c = getchar();
	return k * f;
}
int tong[1000010], ans = 0;
int main() {
    int t = read();
    while(t--) {
        int n = read(); ans = 0;
        memset(tong, 0, sizeof(tong));
        for(int i = 1; i <= n; ++i) {
        	int x = read();
        	ans = max(tong[x], ans);
        	++tong[1]; ++tong[x];
        	for(int j = 2; j * j <= x; ++j) {
        		if(x % j == 0) {
        			++tong[j];
					if(x/j != j) ++tong[x/j];
				}
			}
		}
		printf("%d
", ans);
    }
    return 0;
}

EVEDG

如果图的边数为偶数，则将所有点都划分到一个集合里即可
如果为边数为奇数
1. 如果图中有一个点的度数为奇数，将这个点单独划为一个集合，其他点为另一个集合
2. 如果所有点的度数都为偶数，先将一个有出度的点划为一个集合，然后就会变成上面的情况，即有至少一个点的度数会变成奇数。此情况需要三个集合

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#define LL long long
using namespace std;
LL read() {
	LL k = 0, f = 1; char c = getchar();
	while(c < '0' || c > '9') {
		if(c == '-') f = -1;
		c = getchar();
	}
	while(c >= '0' && c <= '9')
		k = k * 10 + c - 48, c = getchar();
	return k * f;
}
int du[100010];
struct zzz {
	int t, nex;
}e[100010 << 1]; int head[100010], tot;
inline void add(int x, int y) {
	e[++tot].t = y;
	e[tot].nex = head[x];
	head[x] = tot;
}
int main() {
    int t = read();
    while(t--) {
        int n = read(), m = read(); tot = 0;
        for(int i = 1; i <= n; ++i) du[i] = 0, head[i] = 0;
        for(int i = 1; i <= m; ++i) {
        	int x = read(), y = read();
        	++du[x], ++du[y];
        	add(x, y); add(y, x);
		}
        if(!(m & 1)) {
        	printf("1
");
        	for(int i = 1; i <= n; ++i)
        		printf("1 ");
		}
		else {
			bool flag = 0;
			for(int i = 1; i <= n; ++i)
				if(du[i] & 1) flag = 1;
			if(flag) {
				flag = 0;
				printf("2
");
				for(int i = 1; i <= n; ++i)
					if((du[i] & 1) && flag == 0) printf("2 "), flag = 1;
					else printf("1 ");	
			}
			else {
				int pos = 0;
				for(int x = 1; x <= n; ++x)
					if(du[x]) {
						for(int i = head[x]; i; i = e[i].nex) --du[e[i].t];
						pos = x; break;
					}
				printf("3
");
				for(int i = 1; i <= n; ++i)
					if(i == pos) printf("3 ");
					else if((du[i] & 1) && flag == 0) printf("2 "), flag = 1;
					else printf("1 ");
			}
		}
		printf("
");
    }
    return 0;
}

MSNG

直接暴力模拟就好了

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#define LL long long
#define ULL unsigned long long
#define lim 1000000000000ll
using namespace std;
LL read() {
	LL k = 0, f = 1; char c = getchar();
	while(c < '0' || c > '9') {
		if(c == '-') f = -1;
		c = getchar();
	}
	while(c >= '0' && c <= '9')
		k = k * 10 + c - 48, c = getchar();
	return k * f;
}
struct zzz {
	int len, maxx; LL opt, a[51];
}x[110];
int n;
bool judge(LL k) {
	if(k > lim) return 0;
	for(int i = 2; i <= n; ++i) {
		bool flag = 0;
		for(LL j = x[i].maxx; j <= 36; ++j) {
			LL a = 0;
			for(int o = 1; o <= x[i].len; ++o) {
				a = a * j + x[i].a[o];
				if(a > lim) return 0;
			}
			if(a == k) {
				flag = 1; break;
			}
		}
		if(!flag) return 0;
	}
	return 1;
}
int main() {
    int t = read();
    while(t--) {
    	n = read();
    	memset(x, 0, sizeof(x));
    	for(int i = 1; i <= n; ++i) {
    		x[i].opt = read();
    		char s[51]; scanf("%s", s+1);
    		int len = strlen(s+1);
    		x[i].len = len;
    		for(int j = 1; j <= len; ++j) {
    			if(s[j] >= '0' && s[j] <= '9')
    				x[i].a[j] = s[j] - '0';
    			else x[i].a[j] = s[j] - 'A' + 10;
    			x[i].maxx = max((LL)x[i].maxx, x[i].a[j] + 1);
    		}
		}
		for(int i = 2; i <= n; ++i) {
			if(x[1].opt != -1) break;
			if(x[i].opt != -1) {
				swap(x[1], x[i]);
				break;
			}
			if(x[i].maxx > x[1].maxx) swap(x[1], x[i]);
			else if(x[i].maxx == x[1].maxx && x[i].len > x[1].len) swap(x[1], x[i]);
			else if(x[i].maxx == x[1].maxx && x[i].len == x[1].len) {
				for(int j = 1; j <= x[i].len; ++j)
					if(x[i].a[j] > x[1].a[j]) {
						swap(x[1], x[i]); break;
					}
			}
		}
		
		LL k = 0;
		if(x[1].opt != -1) {
			for(int i = 1; i <= x[1].len; ++i) {
				k = k * x[1].opt + x[1].a[i];
				if(k > lim) break;
			}
			if(!judge(k)) printf("-1
");
			else printf("%lld
", k);
		}
		else {
			bool flag = 0;
			for(LL o = x[1].maxx; o <= 36; ++o) {
				k = 0;
				for(int i = 1; i <= x[1].len; ++i) {
					k = k * o + x[1].a[i];
					if(k > lim) break;
				}
				//cout << k << endl;
				if(judge(k)) {
					printf("%lld
", k); flag = 1;
					break;
				}
			}
			if(!flag) printf("-1
");
		}
	}
    return 0;
}

BACREP

每过一秒，点权会下移。设点(x)的深度为(deth_x)，一个修改操作的时间是(t)，被修改的点(i)的深度为点(deth_i)，当前时间是(T)，只有当(deth_x - T = deth_i - t)、且(x)为(i)的后代时时，点(x)才会受这次修改影响。叶子节点需要特殊处理，它会受到所有(deth_x - T leq deth_i - t)的修改的影响
考虑如何用线段树来维护(deth_x - T)
将操作离线，然后进行(dfs)，对每个节点(x)，枚举和它有关的所有操作，设该操作进行的时间为(t)。如果为修改，就在(deth_x - t)的位置加上修改的值(k)。如果是非叶子结点的询问，直接查询(deth_x - t)。如果是叶子节点的询问，则查询区间([deth_x-t,MAXN])
在回溯时要将所有的修改操作撤回，防止对其他子树造成影响

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
#define LL long long
#define ls p << 1
#define rs p << 1 | 1
#define mid ((l+r) >> 1)
#define eps 500005
using namespace std;
LL read() {
	LL k = 0, f = 1; char c = getchar();
	while(c < '0' || c > '9') {
		if(c == '-') f = -1;
		c = getchar();
	}
	while(c >= '0' && c <= '9')
		k = k * 10 + c - 48, c = getchar();
	return k * f;
}
char read_c() {
	char c = getchar();
	while(c != '?' && c != '+') c = getchar();
	return c;
}
struct zzz {
	int t, nex;
}e[500010 << 1]; int head[500010], tot;
struct hhh {
	bool opt; LL k, tim;
};
vector <hhh> que[500010];
inline void add(int x, int y) {
	e[++tot].t = y;
	e[tot].nex = head[x];
	head[x] = tot;
}
bool leaf[500010];
int f[500010], deth[500010];
LL v[500010], tree[1000020 << 2];
void dfs(int x, int fa) {
	f[x] = fa, deth[x] = deth[fa] + 1; leaf[x] = 1;
	for(int i = head[x]; i; i = e[i].nex) {
		if(e[i].t != fa) dfs(e[i].t, x);
		else continue;
		leaf[x] = 0;
	}
}
inline void up(int p) {
	tree[p] = tree[ls] + tree[rs];
}
LL query(int pos, int l = 1, int r = 1000010, int p = 1) {
	if(l == r) return tree[p];
	if(pos <= mid) return query(pos, l, mid, ls);
	else return query(pos, mid+1, r, rs);
}
LL sum(int nl, int nr, int l = 1, int r = 1000010, int p = 1) {
	if(l >= nl && r <= nr) return tree[p];
	LL anss = 0;
	if(nl <= mid) anss += sum(nl, nr, l, mid, ls);
	if(nr > mid) anss += sum(nl, nr, mid+1, r, rs);
	return anss;
}
void update(int pos, LL k, int l = 1, int r = 1000010, int p = 1) {
	if(l == r) {
		tree[p] += k; return ;
	}
	if(pos <= mid) update(pos, k, l, mid, ls);
	else update(pos, k, mid+1, r, rs);
	up(p);
}
LL ans[500010]; bool vis[500010];
void dfs2(int x, int fa) {
	int len = que[x].size();
	update(deth[x] + eps, v[x]);
	for(int i = 0; i < len; ++i) {
		hhh a = que[x][i];
		if(a.opt == 1) {
			int pos = deth[x] - a.tim + eps;
			update(pos, a.k);
		}
		else {
			vis[a.tim] = 1;
			if(!leaf[x])
				ans[a.tim] = query(deth[x] - a.tim + eps);
			else {
				ans[a.tim] = sum(deth[x] - a.tim + eps, 1000010);
			}
		}
	}
	
	for(int i = head[x]; i; i = e[i].nex)
		if(e[i].t != fa) dfs2(e[i].t, x);
		
	update(deth[x] + eps, -v[x]);
	for(int i = 0; i < len; ++i) {
		hhh a = que[x][i];
		if(a.opt == 1) {
			int pos = deth[x] - a.tim + eps;
			update(pos, -a.k);
		}
	}
}
int main() {
	int n = read(), q = read();
	for(int i = 1; i <= n-1; ++i) {
		int x = read(), y = read();
		add(x, y); add(y, x);
	}
	for(int i = 1; i <= n; ++i) v[i] = read();
	dfs(1, 0);
	
	for(int i = 1; i <= q; ++i) {
		char opt = read_c();
		int x = read();
		if(opt == '+') que[x].push_back((hhh){1, read(), i});
		else que[x].push_back((hhh){0, -1, i});
	}
	dfs2(1, 0);
	for(int i = 1; i <= q; ++i)
		if(vis[i]) printf("%lld
", ans[i]);
		
    return 0;
}

MAXLIS

真不会，乱搞只搞到了(4.4)分……