T1 方程（ \(equation\) ）
题面：
给定 \(4\) 个正整数 \(a\), \(b\), \(c\), \(d\)，并且保证 \(c\) \(×\) \(d\) \(≤\) \(10^6\)，请你求出有多少组正整数对 \((x, y)\) 满足如下方程：
\[\frac{a}{x}+\frac{b}{c}=\frac{d}{y} \]本题共 \(20\) 个测试点，每个测试点 \(5\) 分。
• 对测试点 \(1\)，保证 \(T = 0\)。
• 对测试点 \(2\) ∼ \(16\)，共 \(15\) 个测试点。\(a\), \(b\), \(c\), \(d\) 四个数中至少存在一个数为 \(1\) 共 \(15\) 种情况，
每个测试点对应一种情况。
• 对测试点 \(17\) ∼ \(20\)，没有特殊约定。
对全部的测试点，保证 \(0 ≤ T ≤ 20\)，\(1 ≤ a, b, c, d ≤ 10^6\)，\(c × d ≤ 10^6\)。
思路：
化一下式子：
先通分：
然后就：
\[cdx-bxy=acy \]\[x(cd-by)=acy \]\[x=\frac{acy}{cd-by} \]因为 \(cd\) 不超过 \(10^6\)，所以直接枚举 \(y\)。
ll a, b, c, d;
ll ans;
int T;
int main(){
T=read();
while(T--) {
ans=0;
a=read(); b=read(); c=read(); d=read();
for(ll y=1; b*y<c*d; ++y) {
if(a*c*y%(c*d-b*y)==0) ++ans;
}
cout<<ans; putchar('\n');
}
}
T2 异或数列 ( \(xor\)）
题面：
R 老师给了你一个数列 \(a_1, a_2, . . . a_n\)。数列中的数都是非负整数。
R 老师会进行 \(q\) 次操作，每次操作会给你两个数字 \(p\), \(x\)，要求你把 \(a_p\) 和 $a_{p+1} 都对 \(x\) 做一次按位异或。每次操作完后，你必须告诉 R 老师，当前的数列里有多少个子区间 \([l, r]\) 满足 \(l ≤ r\) 且区间按位异或和为 \(0\)。
• 对 \(10\%\) 的数据，保证 \(n, m ≤ 100\)。
• 对 \(20\%\) 的数据，保证 \(n, m ≤ 300\)。
• 对 \(40\%\) 的数据，保证 \(n, m ≤ 3000\)。
• 对 \(70\%\) 的数据，保证 \(n, m ≤ 10^5\)，\(a_i
, x ≤ n\)。
• 对 \(100\%\) 的数据，保证 $1 ≤ n, m ≤ 10^6，\(1 ≤ a_i, x ≤ 10^9，1 ≤ p ≤ n\)
思路:
非常套路的，先求一个异或前缀和，区间异或和为 \(0\) 当且仅当 \(r\) 和 \(l-1\) 位置上的异或前缀和相等，初始的答案很好算，从左往右扫过去就行。
显然的，原数组就是前缀和数组的差分数组，所以题目让把 \(a_p\) 和 \(a_{p+1}\) 都异或 \(x\)，就是让 \(p\) 位置的前缀和数组异或上 \(x\)。
那么他产生的贡献就是，先把原来的贡献减掉，然后这个点作为右端点把左边与这个位置新的值相同的个数加上，再以这个点为左端点把右边相同的个数加上。
总的看来，就是先把所有的异或前缀和的值存起来，算个数，然后改的时候，把所有和这个位置改之前一样的减去，再把所有和改之后一样的值加上。
\(unordered\)_\(map\) 减小常数。
代码：
int n, m, p, x;
int sz[1000006];
ll ans;
unordered_map<int, int>mp;
int main(){
n=read(); m=read();
mp[0]++;
for(int i=1; i<=n; ++i) {
sz[i]=read();
sz[i]^=sz[i-1];
ans+=mp[sz[i]]++;
}
while(m--) {
p=read(); x=read();
ans-=-1+mp[sz[p]]--;
sz[p]^=x;
ans+=mp[sz[p]]++;
cout<<ans; putchar('\n');
}
}
T3 制胡串问题 ( \(string\) )
题面：
用 \(S_i\) 表示字符串 \(S\) 的第 \(i\) 个字符，我们定义一个 \(01\) 串 \(A\) 可以匹. 配. 一个只含字符 \(0\), \(1\), \(?\)
的字符串 \(B\) 当且仅当如下条件满足：
- \(A\) 和 \(B\) 的长度相等。
- 若 \(B_i = 0\)，则 \(A_i = 0\)。
- 若 \(B_i = 1\)，则 \(A_i = 1\)。
- 若 \(B_i = ?\)，则 \(A_i\) 可以为 \(0\)，也可以为 \(1\)。
现在，R 老师会有 \(q\) 次操作，操作共有两种： - 给定 \([l, r]\)，查询有多少字符串 \(S\)，满足 S 能匹配 \([l, r]\) 内的所有字符串。
- 给定 \(x\) 和一个字符串 \(s\)，将第 \(x\) 个字符串换成 \(s\)。保证 \(s\) 也是长度为 \(n\) 的只含 \(0, 1, ?\)的字符串。
| 测试点编号 | m= | q= | n= |
|---|---|---|---|
| 1∼3 | 102 | 102 | 10 |
| 4~6 | 1003 | 1003 | 10 |
| 7~9 | 1004 | 1004 | 30 |
| 10~12 | 100005 | 500005 | 1 |
| 13~14 | 100006 | 50006 | 30 |
| 15~20 | 100007 | 1000007 | 30 |
思路：
直接 \(30\) 棵线段树。
int n, m, q;
int bj[400100][31];
char c[100010][35];
char s[35];
int ans[31];
int Ans, re;
bool flag;
int sta[31], top;
inline void push_up(int g) {
for(int i=0; i<n; ++i) {
if(bj[g<<1][i]==3||bj[g<<1|1][i]==3) {bj[g][i]=3; continue ;}
if(bj[g<<1][i]==bj[g<<1|1][i]) {bj[g][i]=bj[g<<1][i]; continue ;}
if(bj[g<<1][i]==2||bj[g<<1|1][i]==2) bj[g][i]=min(bj[g<<1][i], bj[g<<1|1][i]);
else bj[g][i]=3;
}
}
inline void push_up2(int g) {
for(int j=1; j<=top; ++j) {
int i=sta[j];
if(bj[g<<1][i]==3||bj[g<<1|1][i]==3) {bj[g][i]=3; continue ;}
if(bj[g<<1][i]==bj[g<<1|1][i]) {bj[g][i]=bj[g<<1][i]; continue ;}
if(bj[g<<1][i]==2||bj[g<<1|1][i]==2) bj[g][i]=min(bj[g<<1][i], bj[g<<1|1][i]);
else bj[g][i]=3;
}
}
inline void build(int g, int l, int r) {
if(l==r) {
scanf("%s", c[l]);
for(int i=0; i<n; ++i) {
if(c[l][i]=='0') bj[g][i]=0;
if(c[l][i]=='1') bj[g][i]=1;
if(c[l][i]=='?') bj[g][i]=2;
}
return ;
}
int mid=l+r>>1;
build(g<<1, l, mid); build(g<<1|1, mid+1, r);
push_up(g);
}
inline void Change(int g, int l, int r, int x) {
if(l==r) {
for(int j=1; j<=top; ++j) {
int i=sta[j];
if(c[l][i]=='0') bj[g][i]=0;
if(c[l][i]=='1') bj[g][i]=1;
if(c[l][i]=='?') bj[g][i]=2;
}
return ;
} int mid=l+r>>1;
if(x<=mid) Change(g<<1, l, mid, x);
else Change(g<<1|1, mid+1, r, x);
push_up2(g);
}
inline void update(int g) {
for(int i=0; i<n; ++i) {
if(bj[g][i]==3||ans[i]==3) {ans[i]=3; flag=0; return;}
if(bj[g][i]==ans[i]) continue ;
if(bj[g][i]==2||ans[i]==2) ans[i]=min(ans[i], bj[g][i]);
else {ans[i]=3; flag=0; return ;}
}
}
inline void SUM(int g, int l, int r, int L, int R) {
if(!flag) return ;
if(L<=l&&r<=R) {
update(g);
return ;
} int mid=l+r>>1;
if(L<=mid) SUM(g<<1, l, mid, L, R);
if(R>mid) SUM(g<<1|1, mid+1, r, L, R);
}
int main(){
n=read(); m=read(); q=read();
build(1, 1, m);
while(q--) {
int op=read();
if(op) {
int x=read(); scanf("%s", s);
top=0;
for(int i=0; i<n; ++i) if(c[x][i]!=s[i]) c[x][i]=s[i], sta[++top]=i;
if(top)
Change(1, 1, m, x);
}
else {
int l=read(), r=read();
for(int i=0; i<n; ++i) ans[i]=2;
flag=1;
SUM(1, 1, m, l, r);
if(!flag) continue ;
re=1;
for(int i=0; i<n; ++i) {
if(ans[i]==2) re*=2;
if(ans[i]==3) {re=0; break;}
}
Ans^=re;
}
}
cout<<Ans;
}
T4 游戏（ \(game\) ）
题面：
这是一款一对一回合制游戏。双方玩家各有一个属性，被称为 \(delay\) 值，简称 \(d\) 值。\(d\) 值会根据回合中玩家使用的道具类型和数量来进行相应的增加。我们定义玩家 \(x\) 的回合为玩家 \(x\) 从发动攻击到结束的整个过程。在玩家 \(x\) 的回合中, 只有玩家 \(x\) 可以使用道具和发动攻击并且玩家 \(x\) 一定会发动攻击。当一个玩家的回合结束以后，下一回合将是两个玩家中 d 值较小的玩家的回合。当两个玩家的 \(d\) 值相同时，因为小 A 氪金很多，下一回合一定是小 A 的回合。
这款游戏共有 \(m\) 种道具，第 \(i\) 种道具会将本回合的伤害增加不计算其他道具的原始伤害的 \(\frac{ki}{10^5}\) 倍，同时会增加 \(p_i\) 点 \(d\) 值。每回合每种道具只能使用一次，本回合的道具不会对下回合产生伤害增益效果。同时，每回合结束以后，发动攻击的玩家一定会增加 \(w\) 点 \(d\) 值。
而使用道具是受到双方 \(d\) 值差限制的。具体的，任何回合所使用的道具应该满足本回合结束以后双方 \(d\) 值（包括发动攻击的玩家一定增加的 \(w\) 点 \(d\) 值）之差的绝对值不. 超. 过.
100。
一个显然的事实是，只要保证了 w ≤ 100，玩家就一定存在一种选择道具的方法（包括不选
择），来满足这个限制。
例如，在小 A 的回合中，若她的原始伤害 t = 105，初始时 d 值 d0 = 3，规定 w = 2，她
使用了两个道具，k1 = 114，k2 = 514，p1 = 19，p2 = 81，那么本回合她造成的伤害为
t + t × k1 + t × k2 = 105 + 114 + 514 = 100628
她回合结束后的 d 值为
d0 + w + p1 + p2 = 3 + 2 + 19 + 81 = 105
而假如下回合还是她的回合，并且她没有使用道具，那么她下回合造成的伤害为
t = 100000
她下回合结束后的 d 值为
第 8 页 共 10 页2022 CCF 非专业级软件能力认证 4 游戏（game）
105 + w = 105 + 2 = 107
现在，小 A 和小 B 在这个游戏中进行单挑。给定游戏的道具列表，和他们的原始伤害、
d 值。游戏一共会进行 n 回合，不妨认为无论造成多大的伤害，双方都不会死亡。请你最大
化「小 A 对小 B 造成的伤害 - 小 B 对小 A 造成的伤害」这个差的值。
当然，小 B 也会尽可能最大化「她对小 A 造成伤害 - 小 A 对她造成伤害」的值。不妨
认为双方都绝顶聪明，也就是他. 们. 都. 会. 选. 择. 最. 优. 的. 策. 略. 来. 使. 用. 道. 具. 而. 不. 会. 出. 错. ，题目所求即
为在这种情况下伤害差的最大值。