CF1703.

自从前几天开始，我就一直用 #define int long long 了。

A. YES or YES?

分析

直接判断即可。

CODE

#include<bits/stdc++.h>
using namespace std;
#define int long long
int t;
int read() {
	int a=0, f=1; char c=getchar();
	while(!isdigit(c)) {
		if(c=='-') f=-1;
		c=getchar();
	}
	while(isdigit(c)) a=a*10+c-'0', c=getchar();
	return a*f;
}
void solve() {
	char s[5];
	scanf("%s",s);
	int fg=1;
	if(s[0]!='y'&&s[0]!='Y') fg=0;
	if(s[1]!='e'&&s[1]!='E') fg=0;
	if(s[2]!='s'&&s[2]!='S') fg=0;
	puts(fg? "YES":"NO");
}
signed main() {
	t=read();
	while(t--) solve();
}

B. ICPC Balloons

分析

对于一个字母，第一次出现就让答案 \(+2\)，否则 \(+1\)。

CODE

#include<bits/stdc++.h>
using namespace std;
#define int long long
int t, n;
map<char,int> p;
int read() {
	int a=0, f=1; char c=getchar();
	while(!isdigit(c)) {
		if(c=='-') f=-1;
		c=getchar();
	}
	while(isdigit(c)) a=a*10+c-'0', c=getchar();
	return a*f;
}
void solve() {
	n=read();
	p.clear();
	string s; cin>>s;
	int ans=0;
	for(auto x:s) {
		if(++p[x]==1) ans+=2; else ans+=1;
	}
	printf("%lld\n",ans);
}
signed main() {
	t=read();
	while(t--) solve();
}

C. Cypher

分析

暴力还原即可。\(Up\) 记为 \(-1\)，\(Down\) 记为 \(+1\)，求出操作和 \(s\)。用原来的数字加上 \(s\)，取模即可。

COED

#include<bits/stdc++.h>
using namespace std;
#define int long long
int t, n, a[105], c[105];
struct B { int t; char moves[20]; } b[105];
map<char,int> p;
int read() {
	int a=0, f=1; char c=getchar();
	while(!isdigit(c)) {
		if(c=='-') f=-1;
		c=getchar();
	}
	while(isdigit(c)) a=a*10+c-'0', c=getchar();
	return a*f;
}
void solve() {
	n=read();
	for(int i=1;i<=n;++i) a[i]=read();
	for(int i=1;i<=n;++i) {
		b[i].t=read();
		scanf("%s",b[i].moves);
	}
	for(int i=1;i<=n;++i) {
		int s=0;
		for(int j=0;j<b[i].t;++j)
			if(b[i].moves[j]=='U') --s; else ++s;
		c[i]=(a[i]+s)%10;
		if(c[i]<0) c[i]=(c[i]+10)%10;
	}
	for(int i=1;i<=n;++i) printf("%lld%c",c[i]," \n"[i==n]);
}
signed main() {
	t=read();
	while(t--) solve();
}

D. Double Strings

分析

由于每个字符串长度不超过 \(8\)，可以看作常数。所以对于字符串 \(S\)，枚举断点 \(p\)，判断两个字符串是否存在即可，注意边界。

用 std::map 实现，复杂度 \(O(n \log_2 n)\)。

一开始竟然想出了，开一颗 Trie，对于字符串 \(s\)，快速查找有没有它的前缀单词，有的话就从那个位置截取字符串，查找是否存在。没实现好，打挂之后就睡觉了。睡前才发现字符串最大长度为 \(8\)，而且貌似快不了多少。菜死了qwq。

CODE

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=1e5+5;
int t, n, tot;
string s[N];
map<string,int> p;
int read() {
	int a=0, f=1; char c=getchar();
	while(!isdigit(c)) {
		if(c=='-') f=-1;
		c=getchar();
	}
	while(isdigit(c)) a=a*10+c-'0', c=getchar();
	return a*f;
}
void solve() {
	n=read();
	p.clear();
	for(int i=1;i<=n;++i) cin>>s[i], p[s[i]]=1;
	for(int i=1;i<=n;++i) {
		int fg=0;
		for(int j=1;j<s[i].length();++j) {
			string t1=s[i].substr(0,j), t2=s[i].substr(j,s[i].size()-j);
			if(p[t1]&&p[t2]) fg=1;
		}
		printf("%d",fg);
	}
	puts("");
}
signed main() {
	t=read();
	while(t--) solve();
}

E. Mirror Grid

分析

定义一个位置 \((x,y)\)“被要求修改”，当且仅当存在一个位置旋转任意度后落在 \((x,y)\)，且与它本身数字不同。

不难发现，对于一个被要求修改位置 \((x,y)\)，早修改和晚修改是等价的。

\((x,y)\) 顺时针旋转 90° 后的位置是 \((y,n-x+1)\)。对于一个 \((x,y)\)，我们只需要枚举包括它在内的 \(4\) 个位置，看有哪些是被要求修改的。

设 \(cnt_0\) 为这四个位置中 \(0\) 的个数，如果 \(cnt_0 = 0\) 或 \(cnt_0 = 4\)，没有位置被要求修改。如果 \(cnt_0 = 1\)，那么最优决策是将这个 \(0\) 改成 \(1\)，需要一次操作，同理若 \(cnt_0 = 3\)，也只需要一次操作将那个 \(1\) 改为 \(0\) 即可。若 \(cnt_0 = 2\)，需要两次操作，随便改。

CODE

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=105;
int t, n, ans;
char s[N][N];
int read() {
	int a=0, f=1; char c=getchar();
	while(!isdigit(c)) {
		if(c=='-') f=-1;
		c=getchar();
	}
	while(isdigit(c)) a=a*10+c-'0', c=getchar();
	return a*f;
}
void solve() {
	n=read();
	ans=0;
	for(int i=1;i<=n;++i) scanf("%s",s[i]+1);
	for(int i=1;i<=n;++i) for(int j=1;j<=n;++j) {
		int x=i, y=j, cnt=0;
		for(int k=1;k<=4;++k) {
			cnt+=s[x][y]=='0';
			int tx=x, ty=y;
			x=ty, y=n-tx+1;
		}
		if(!cnt||cnt==4) continue;
		char o;
		if(cnt==1) o='1', ++ans;
		if(cnt==3) o='0', ++ans;
		if(cnt==2) o='0', ans+=2;
		x=i, y=j;
		for(int k=1;k<=4;++k) {
			s[x][y]=o;
			int tx=x, ty=y;
			x=ty, y=n-tx+1;
		}
	}
	printf("%lld\n",ans);
}
signed main() {
	t=read();
	while(t--) solve();
}

F. Yet Another Problem About Pairs Satisfying an Inequality

分析

有一个我自己总结出来的小结论：在一个序列问题中，对于下标 \(i\)，更容易统计 \([1,i-1]\) 这部分的信息。

考虑维护一个序列，对于下标 \(x\)，只有满足 \(a_x < x\) 才将 \(x\) 加入。那么如果手里有一个 \(i\) 满足 \(a_i < i\)，只要在这个序列中统计小于 \(a_i\) 的元素的数量，就是 \([1,i-1]\) 和 \(i\) 对答案产生的贡献。

具体地，使用 std::lower_bound()，查找序列内第一个大于等于 \(a_i\) 的数，设它的下标为 \(k\)，那么贡献即为 \(k-1\)。

CODE

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=2e5+5;
int t, n, a[N];
vector<int> v;
int read() {
	int a=0, f=1; char c=getchar();
	while(!isdigit(c)) {
		if(c=='-') f=-1;
		c=getchar();
	}
	while(isdigit(c)) a=a*10+c-'0', c=getchar();
	return a*f;
}
void solve() {
	n=read();
	v.clear();
	for(int i=1;i<=n;++i) a[i]=read();
	int ans=0;
	for(int i=1;i<=n;++i) {
		if(a[i]>=i) continue;
		int k=lower_bound(v.begin(),v.end(),a[i])-v.begin();
        // vector下标从0开始，所以不用-1
		ans+=k;
		v.push_back(i);
	}
	printf("%lld\n",ans);
}
signed main() {
	t=read();
	while(t--) solve();
}

G. Good Key, Bad Key

分析

大胆猜想一个结论：在最优解中使用坏钥匙的，一定是一段后缀。

证明：

邻项交换法。假设 \(i\) 使用了坏钥匙，\(i+1\) 使用了好钥匙，那么收益为 \(\lfloor \frac{a_i}{2} \rfloor + \lfloor \frac{a_{i+1}}{2} \rfloor - k\)；反过来，假设 \(i\) 使用了好钥匙，\(i+1\) 使用了坏钥匙，那么收益为 \(a_i + \lfloor \frac{a_{i+1}}{2} \rfloor - k\)。后者显然小于前者，所以最优解中，使用坏钥匙的一定是一段后缀，命题成立。

从 \(0\) 到 \(n\) 枚举使用坏钥匙的数量，同时也是倒序枚举好钥匙的数量。

由于每多用一把坏钥匙，后面的收益都要减半，所以使用 std::set 来维护这个「减半集合」。设 \(s_i = \sum_{j=1}^i a_j\)，则使用 \(i\) 把好钥匙的收益为 $ = s_i - i k$。此时集合里维护了在 \([i+1,n]\) 每个箱子都使用坏钥匙后，每个箱子的收益。将 \(\Delta\) 加上所有集合里的数，就得到了总收益，取最大值即可。

如何维护？当求出使用 \(i\) 把好钥匙的收益后，将 \(\lfloor \frac{a_i}{2} \rfloor\) 加入集合，同时将集合内所有元素都除以 \(2\) 并下取整。由于 std::set 不便于直接修改，可以新开一个 std::set 来储存修改后的元素，然后交换两个集合。

由于最大的元素不超过 \(10^9\)，\(\lfloor \log_2(10^9) \rfloor = 29\)，所以可以认为每个元素进出集合常数次，复杂度 \(O(n \log_2 n)\)。

CODE

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=2e5+5;
int t, n, k, a[N], s[N];
multiset<int> st, tmp;
int read() {
	int a=0, f=1; char c=getchar();
	while(!isdigit(c)) {
		if(c=='-') f=-1;
		c=getchar();
	}
	while(isdigit(c)) a=a*10+c-'0', c=getchar();
	return a*f;
}
void solve() {
	st.clear();
	n=read(), k=read();
	for(int i=1;i<=n;++i) a[i]=read(), s[i]=s[i-1]+a[i];
	int ans=0;
	for(int i=n;~i;--i) {
		int dlt=s[i]-i*k;
		for(auto x:st) dlt+=x;
		ans=max(ans,dlt);
		tmp.clear();
		if(a[i]/2>0) tmp.insert(a[i]/2);
		for(auto x:st) if(x/2) tmp.insert(x/2);
		swap(st,tmp);
	}
	printf("%lld\n",ans);
}
signed main() {
	t=read();
	while(t--) solve();
}