CSP2020-S

T1 儒略日(julian)

(Waiting Updating)

T2 动物园(zoo)

题目大意：

这个题大概就是说每种动物编号的二进制位中是 \(1\) 的位对应了这种动物所需要的饲料之一，让你去求在当前饲料供给条件下，还能多饲养多少动物。

仔细想一下会发现，其实并没有必要去维护所谓的饲料种类 \(c\) 。这取决于题面中一条很重要的性质，就是保证 \(q_i\) 互不相同。

这样的话就只会出现一个二进制位对应多种饲料，而不会出现一种饲料对应多个二进制位的情况，这样的话就可以考虑用 \(p_i\) 来维护所需要的饲料种数。

考虑相同的二进制位对饲料种类的贡献是重叠的，所以就可以把所有的已有的动物编号或起来，然后对于给定的每一个 \(p_i\) ，看一下对应的二进制位是否为 \(1\) 。

如果为 \(1\) ， 那编号二进制此位为 \(1\) 的动物就可以添加进来饲养， 若为 \(0\) 就会导致饲料种类发生变化，不可以饲养。

这样最后的结果就是 \(2^{k - cnt} - n\) , \(cnt\) 为会导致饲料种类发生变化的二进制位个数。

最后，这个题有两个坑点：一是对于相同的 \(p_i\) ，只能统计一次；二是当 \(n = 0\) 且 \(k = 64\) 时，答案会爆 \(unsigned　long　long\) ， 需要特判一下。

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<map>
#define MAXN 1000005
typedef unsigned long long ull;
int n, m, c, k, cnt;
int p[MAXN], q[MAXN];
ull a[MAXN], al;
std::map<int, int> M;
template <class I> inline void read(I &x){
    x = 0; int f = 1; char ch;
    do { ch = getchar(); if(ch == '-') f = -1; } while(ch < '0' || ch > '9');
    do { x = (x << 1) + (x << 3) + (ch ^ 48); ch = getchar(); } while(ch >= '0' && ch <= '9');
    x *= f; return;
}
template <class I> inline void write(I x){
    if(x < 0) { putchar('-'); x = -x; }
    if(x > 9) write(x / 10);
    putchar( x % 10 + '0');
}
int main(){
    //freopen("zoo.in", "r", stdin);
    //freopen("zoo.out", "w", stdout);
    read(n), read(m), read(c), read(k);
    for(int i = 1; i <= n; ++i) read(a[i]), al |= a[i];
    for(int i = 1; i <= m; ++i) read(p[i]), read(q[i]);
    for(int i = 1; i <= m; ++i)
        if(((al >> p[i]) & 1) == 0 && !M.count(p[i])) ++cnt, M[p[i]] = 1;
    if(n == 0 && k == 64) puts("18446744073709551616");
    else write(((ull)1 << (k - cnt)) - n);
    return 0;
}

函数调用(call)

由于考场上持续刚T1，导致T3T4基本没怎么看/kk

出考场以后发现有个线段树的暴力做法还是挺简单的（但是就是没空写了）

导致我白白丢了70pts……

下面进入正题：

首先考虑怎么去处理乘法和加法操作：

想一想可以发现，对于一个操作序列 $ a_i + p , a_i \times q $ , 可以将其转化为 $ a_i \times q , a_i + p \times q $ 。

由此可知，可以把先加后乘的操作序列修改为先乘后加的操作序列， 且修改后加法操作相当于进行了 $ q $ 次。

然后考虑操作的调用。由题目中的约束条件可知，所有操作调用构成一张DAG。因此，考虑建立一个超级原点， 这个点连向所有初始调用的操作，这样就构成了一棵以 0 为原点的操作树。

考虑按 “左 -> 右 -> 中” 对该树进行遍历， 更新出执行到该点时全局乘上的值， 也就相当于执行次数。

考虑操作树上的每一个点时， 连向该点的边应当全部被处理完， 即入度为 0 , 所以考虑用拓扑排序来解决这个问题。

当拓扑到一个点时，该点的执行次数相当于该点的父节点的执行次数 + 该点父节点调用的操作当中在该操作之后的操作的执行次数。

这样做的理由就是对于每个点而言，它的影响因子是在它之后的所有点（之前的处理到该点时已经确定了）。

所以这样整体思路就有了。具体细节看代码：

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<queue>
#include<vector>
#define MAXN 100005
#define MOD 998244353
typedef long long ll;
int n, m, q, a[MAXN];
std::vector<int> g[MAXN];
ll mul[MAXN], add[MAXN];
int in[MAXN], t[MAXN];
bool vis[MAXN];
struct Reservation{
	int opt;
	int pos, val;
} ipt[MAXN];
template <class I> inline void read(I &x){
    x = 0; int f = 1; char ch;
    do { ch = getchar(); if(ch == '-') f = -1; } while(ch < '0' || ch > '9');
    do { x = (x << 1) + (x << 3) + (ch ^ 48); ch = getchar(); } while(ch >= '0' && ch <= '9');
    x *= f; return;
}
void DFS(int k){
	vis[k] = 1;
	mul[k] = 1;
	if(ipt[k].opt == 1) return;
	if(ipt[k].opt == 2){
		mul[k] = ipt[k].val;
		return;
	}
	for(int i = 0; i < g[k].size(); ++i){
		if(!vis[g[k][i]]) DFS(g[k][i]);
		mul[k] = (mul[k] * mul[g[k][i]]) % MOD;
	}
	return;
}
void Toposort(void){
	std::queue<int> Q;
	for(int i = 0; i <= m; ++i) if(!in[i]) Q.push(i);
	t[0] = 1;
	while(!Q.empty()){
		int u = Q.front();
		Q.pop();
		int ti = t[u];
		for(int i = g[u].size() - 1; i >= 0; --i){//主要就是这个循环
			int v = g[u][i];
			if(!--in[v]) Q.push(v);
			t[v] = (1ll * t[v] + ti) % MOD;//更新该点操作次数，ti表示的就是该点在此轮调用中的执行次数
			if(ipt[v].opt == 1) add[ipt[v].pos] = (add[ipt[v].pos] + 1ll * ipt[v].val * ti % MOD) % MOD;//更新加法标记
			ti = (1ll * ti * mul[v]) % MOD;//更新下一个点的执行次数
		}
	}
	return;
}
int main(){
	//freopen("call.in", "r", stdin);
	//freopen("call.out", "w", stdout);
	read(n);
	for(int i = 1; i <= n; ++i) read(a[i]);
	read(m);
	for(int i = 1; i <= m; ++i){
		read(ipt[i].opt);
		if(ipt[i].opt == 1) read(ipt[i].pos), read(ipt[i].val);
		if(ipt[i].opt == 2) read(ipt[i].val);
		if(ipt[i].opt == 3){
			read(ipt[i].pos);
			for(int j = 1; j <= ipt[i].pos; ++j)
				read(ipt[i].val), g[i].push_back(ipt[i].val), ++in[ipt[i].val];
		}
	}
	read(q);
	for(int i = 1, ue; i <= q; ++i){
		read(ue);
		g[0].push_back(ue);
		++in[ue];
	}
	ipt[0].opt = 3;
	DFS(0);
	Toposort();
	for(int i = 1; i <= n; ++i) a[i] = (1ll * a[i] * mul[0] % MOD + add[i]) % MOD;
	for(int i = 1; i <= n; ++i) printf("%d ", a[i]);
	puts("");
	return 0;
}

贪吃蛇(snakes)

(Waiting Updating)