2022 icpc南京（I,G,A,D,M,B）

题意：

给定长度为n的字符串，令f(S,d)表示将S左移d次后获 得的字符串。若对于所有非负整数d，f(S,d)都是回文串， 则称S为完美回文。 每次操作可以修改一个字母，求将A变为完美回文的最少操作次数

完美回文串必须所有字符均相等
所以枚举将整个字符串全变成a,全变成b,全变成c...,答案取最优即可

#include<bits/stdc++.h>
#define endl '\n'
#define int long long
using namespace std;
string s;
void solve() {
	cin>>s;
	map<char,int>mp;
	for(int i=0;i<(int)s.size();i++) mp[s[i]]++;
	int ans=2e9;
	for(char ch='a';ch<='z';ch++){
		ans=min(ans,(int)s.size()-mp[ch]);
	}
	cout<<ans<<endl;
}
signed main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	int t=1;
    cin>>t;
	while(t--) {
		solve();
	}
	return 0;
}

题意：

维护一个序列，序列里一开始只有一个1。您要处理n个事 件，每次要么往序列里添加一个1，要么从序列里拿出两个 数，加起来再放回去，要么在这两种事件中选一个。 在每次都能从序列里拿出两个数的前提下，求序列平均值的 最大值

首先我们分别分析一下两种操作
先整体感受一下
1.往序列里添加一个1,那么平均数变为(sum+1)/(cnt+1),平均数会趋向1,如果操作前平均数小于1,那么操作后平均数变大;如果操作前平均数大于1,那么操作后平均数变小;如果操作前平均数等于1,那么操作后平均数不变
2.将序列的两个数相加,替换成一个数,那么平均数就是sum/(cnt-1),平均数一定是变大的
这样整体感受一下,猜测2是更优的,但是当平均数小于1时,其实并不知道哪个操作平均数增加的更多
总归还是得用数学公式严格推导:
假设(sum+1)/(cnt+1)>sum/(cnt-1)
==>(sum+1)*(cnt-1)>sum*(cnt+1)
==>sum<cnt/2-1/2
也就是说只有当sum<cnt/2-1/2时,做操作1后的平均数比做操作2后的平均数大
但是sum肯定是大于等于cnt的,因为每个数都大于等于1,所以sum不可能小于cnt/2-1/2,故操作2肯定更优

故我们的贪心策略就是如果它确定选择某个操作,那么没办法只能做,如果自己选择的话,肯定优先选择操作2,但是做操作2有一个限制,就是个数必须大于等于2,所以我们在贪心的过程中,如果选择操作2的时候个数小于2,那么就反悔,记录前面让我们自己选择时我们选择了2的个数,然后将2改为1,直到个数大于等于2,如果反悔都不能让个数大于等于2,那么无解,输出-1

#include <bits/stdc++.h>
#define endl '\n'
#define int long long
using namespace std;
const int N = 1e6 + 10;
int a[N];
int n;
int gcd(int a,int b){
	if(b==0) return a;
	return gcd(b,a%b);
}
void solve() {
	cin >> n;
	for (int i = 1; i <= n; i++) cin >> a[i];
	int tot = 0; //自己选择时选择了2的个数
	int sum = 1, cnt = 1;//注意,初始时就有1个数
	for (int i = 1; i <= n; i++) {
		if (a[i] == 1) sum++, cnt++;
		else if (a[i] == -1) {
			if (cnt >= 2) cnt--;
			else {
				while (cnt < 2 && tot > 0) {
					tot--;
					sum++;
					cnt += 2; //将操作2变为操作1,相当于多了两个数
				}
				if (cnt < 2) {
					cout << -1 << endl;
					return;
				}
				cnt--;
			}
		} else {
			if (cnt >= 2) { //选择2
				cnt--;
				tot++;
			} else { //选择1
				sum++;
				cnt++;
			}
		}
	}
	int d=gcd(sum,cnt);
	sum/=d;
	cnt/=d;
	cout << sum << ' ' << cnt << endl;
}
signed main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	int t = 1;
	cin >> t;
	while (t--) {
		solve();
	}
	return 0;
}

题意：

给定一张n行m列的网格，在位于第i行第j列的格子 上有一个洞，其它每个格子都是空地并且都有一只袋鼠。 所有袋鼠会同时根据按下的U，D，L，R按键移动，如果一 只袋鼠踩到了洞或者移动到了网格外面，它将被从网格上移 除。 给出长度为l的一个操作序列，若执行后网格上恰有k只袋 鼠存留，求出有多少位置可能存在洞

首先我们先考虑出界的情况,我们只要按照操作顺序操作,看有哪些行,哪些列会跑到0行,n+1行,0列,m+1列,那么这些行和列均会出界
就是我们分别记录操作的前缀U,D方向和前缀L,R方向的最终结果,比如说枚举到某个操作,前缀U,R为3,说明向上移动了3行,那么第3行的就移动到了第0行,那么第3行的就会全部出界
(当然,有一个trcik,运动是相对的,我们可以考虑让边界反向移动,边界外的就是出界的)
总之,我们会发现没有出界的是一个矩形,它太规则了,规则到我们可以把它看作一个整体,同时对它们进行操作,所以就按照操作顺序走一遍,由于只有一个洞,假设洞为(x,y),那么就看几只袋鼠会经过(x,y)那么就有几只袋鼠会掉入洞中,所以我们就把矩形经过的地方均+1,那么对于某个洞,加了多少次,就有几只袋鼠经过,但是如果某一只袋鼠经过了某个点,加了一次,它又走回来,那是不能再加一次的,所以需要判重,就是某个矩形位置已经走过了,那这个矩形位置就不再加1了(矩阵大小是固定的,看作一个整体,用左上角坐标代表整个矩阵),很显然用二维差分进行矩形整体加1,再用二维前缀和还原每个点加了多少

#include<bits/stdc++.h>
#define endl '\n'
#define int long long
using namespace std;
typedef pair<int,int>PII;
const int N=1e3+20;
int a[N][N];
int n,m,k;
string s;
void insert(int x1,int y1,int x2,int y2,int c){
	a[x1][y1]+=c;
	a[x1][y2+1]-=c;
	a[x2+1][y1]-=c;
	a[x2+1][y2+1]+=c;
}
void solve() {
	cin>>n>>m>>k;
	cin>>s;
	for(int i=0;i<=n+10;i++){
		for(int j=0;j<=m+10;j++){
			a[i][j]=0;
		}
	}
	int L=1,R=m;
	int U=1,D=n;
	int u=1,d=n,l=1,r=m;
	for(int i=0;i<(int)s.size();i++){
		if(s[i]=='U') u++,d++;
		else if(s[i]=='D') u--,d--;
		else if(s[i]=='L') l++,r++;
		else l--,r--;
		U=max(U,u),D=min(D,d),L=max(L,l),R=min(R,r);
	}
	if(U>D||L>R){
		if(k==0) cout<<n*m<<endl;
		else cout<<0<<endl;
		return;
	}
	if((D-U+1)*(R-L+1)<k){
		cout<<0<<endl;
		return;
	}
	map<PII,bool>mp;
	insert(U,L,D,R,1);
	mp[{U,L}]=true;
	for(int i=0;i<(int)s.size();i++){
		if(s[i]=='U') U--,D--;
		else if(s[i]=='D') U++,D++;
		else if(s[i]=='L') L--,R--;
		else L++,R++;
		if(!mp.count({U,L})) mp[{U,L}]=true,insert(U,L,D,R,1);
	}
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			a[i][j]+=a[i-1][j]+a[i][j-1]-a[i-1][j-1];
		}
	}
	int ans=0;
	int res=(D-U+1)*(R-L+1);
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			if(res-a[i][j]==k) ans++;
		}
	}
	cout<<ans<<endl;
}
signed main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	int t=1;
    cin>>t;
	while(t--) {
		solve();
	}
	return 0;
}

题意：

给定一个长度为n的整数序列a1,a2,··· ,an，同时给定另外 四个整数k，m，c与d，可以进行以下操作至多一次：选择 一个长度恰为m的连续子数组，并将一个长度为m，首项 为c，公差为d的等差序列加到该连续子数组上。 最大化序列中第k大的值

求什么的最大值,想到二分
求最大的第k大的值,那么check某个数x时,只需要保证第k大的数大于等于x就返回true,因为我们要的是最大的第k大的数,那么第k大的数大于等于x就继续往大了找,最终找到的就是第k大的数刚好等于x,此时x是最大的
如何判断第k大的数大于等于x呢？只要大于等于x的数的个数大于等于k
那么如果数本来就大于等于x,那么不需要操作,肯定大于等于x了,那么对于某个区间操作之后,我们要知道有多少数从小于x变成大于等于x了,而且我们要知道每个区间操作之后,分别有多少数从小于x变成大于等于x了

有这样一个trick:区间长度固定为m,那么就将整个区间看作一个整体,用左端点来代表整个区间,之前在cf见过Codeforces Round 974 (Div. 3) D. Robert Hood and Mrs Hood-CSDN博客

还有一个trick:对于一个区间操作，我们想知道有多少数从小于x变成大于等于x了 ,我们只需要按顺序将整个区间操作一遍，然后求出有几个就行了，然后每个区间的话，就是分别对每个区间操作一遍，但是这样会超时

我们反过来，上面是对每一个区间，这里我们就对每一个数，看有哪些区间（左端点代表一个区间）可以让该数从小于x变成大于等于x，将这些区间（左端点代表一个区间 ）加1，这样就统计出对每个区间操作有几个数从小于x变成大于等于x了

由于对于一个数来说，合法的区间肯定是连续的，显然差分

#include<bits/stdc++.h>
#define endl '\n'
#define int long long
using namespace std;
const int N=2e5+10;
int n,k,m,c,d;
int a[N];
int b[N];
bool check(int x){
	int sum=0;
	for(int i=1;i<=n;i++) sum+=(a[i]>=x);
	for(int i=1;i<=n+1;i++) b[i]=0;
	for(int i=1;i<=n;i++){
		if(a[i]<x){
			int l=0,r=1e9;
			while(l<r){
				int mid=l+r>>1;
				if(a[i]+c+mid*d>=x) r=mid;
				else l=mid+1;
			}
			int pos=i-l;
			if(i-pos+1>m||pos<1) continue;
			int L=max(1ll,i-m+1),R=pos;
			b[L]++,b[R+1]--;
		}
	}
	for(int i=1;i<=n;i++) b[i]+=b[i-1];
	for(int i=1;i<=n;i++){
		if(sum+b[i]>=k) return true;
	}
	return false;
}
void solve() {
	cin>>n>>k>>m>>c>>d;
	for(int i=1;i<=n;i++) cin>>a[i];
	int l=0,r=1e18;
	while(l<r){
		int mid=l+r+1>>1;
		if(check(mid)) l=mid;
		else r=mid-1;
	}
	cout<<l<<endl;
}
signed main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	int t=1;
//    cin>>t;
	while(t--) {
		solve();
	}
	return 0;
}

题意：

给定一个由n个顶点组成的多边形水箱，里面充满水。 求至少需要安装多少个出水阀门，才能在所有阀门同时打开 后，让水箱里的水全部流出

每个局部最低点都要安装一个出水阀门，因此本题求的就是局部最低点的数量。局部最低点可以按是否位于水平的平台上分成两种情况：在平台上和不在平台上

点是逆时针顺序给的
两种情况:
1.V字形,必须是先往右下再往左上的那种,贡献加1,这种情况叉积>0
2.U字形,必须是先下再水平再上的那种,且一定是从左往右，贡献加1

#include<bits/stdc++.h>
#define endl '\n'
#define int long long
using namespace std;
const int N=2e3+10;
int x[N],y[N];
int cross(int x1,int y1,int x2,int y2){//向量的叉积
	return x1*y2-x2*y1;
}
int n;
void solve() {
	cin>>n;
	for(int i=0;i<n;i++) cin>>x[i]>>y[i];
	int ans=0;
	for(int i=0;i<n;i++){
		int j=i;
		while(y[j]==y[i]) j=(j+1)%n;
		int pre=(i-1+n)%n;
		if(y[i]<y[pre]&&y[i]<y[j]){
			if(y[i]!=y[(i+1)%n]){
				if(cross(x[i]-x[pre],y[i]-y[pre],x[j]-x[i],y[j]-y[i])>0) ans++;
			}
			else{
				if(x[(i+1)%n]>x[i]) ans++;
			}
		}
	}
	cout<<ans<<endl;
}
signed main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	int t=1;
//    cin>>t;
	while(t--) {
		solve();
	}
	return 0;
}

题意：

在距离索道入口0和(n+1)单位距离的位置有索道站，给 出在1,2,··· ,n 单位距离架设支撑塔的成本，分别是 a1, a2,··· ,an。要求相邻支撑塔或索道站之间的距离必须小 于等于k。 成本序列会进行q次临时的修改（之后会复原），求出架设 支撑塔的最小总成本

首先考虑修改前,可以进行dp,dp[i]表示在第i个位置架设支撑塔的基础上的最小成本,转移的话,就从[i-k+1,i-1]转移过来,在长度为k的固定区间选取一个最小的dp[j]转移过来,这样的话时间复杂度是O(n^2)
有些位置是必须选择的,那么如果遇到某个位置必须选择,那么就将优先队列清空,将其放进去,保证它肯定被选择了

如何快速求滑动窗口的最小值,这是单调队列的一个应用

算法：单调队列_单调队列算法-CSDN博客

现在考虑修改,比如对第i个进行修改,那么dp[1],dp[2],...dp[i-1]是不受影响的,dp[i],dp[i+1],...dp[n+1]均受影响,重新维护肯定会超时,于是我们需要提前预处理last[i]表示在第i个位置架设支撑架的后缀最小成本,那么实际上如果第i个位置架设了支撑架的话,总的最小成本就是dp[i]+last[i]-a[i],减去a[i]是因为前缀已经算过一次了
所以我们只要确定某个位置i架设了支撑架,那么总体的最小成本就能立马算出来,由于长度为k的区间里必须有一个位置建设支撑架,否则学校相邻支撑架的距离大于k,那么我们只要计算一下dp[i],dp[i+1],...dp[i+k-1](k很小,这一部分枚举一遍即可),然后取最小的dp[j]+last[j]-a[j]

#include<bits/stdc++.h>
#define endl '\n'
#define int long long
using namespace std;
const int N=5e5+10;
int a[N];
int dp[N],last[N];
int tmp[N];
int n,k,Q;
string s;
void init(){
	deque<int>q;
	dp[0]=0;
	a[0]=0;
	q.push_back(0);
	for(int i=1;i<=n+1;i++){
		dp[i]=dp[q.front()]+a[i];
		if(s[i]=='1'){
			q.clear();
			q.push_back(i);
		}
		else{
			if(q.size()&&i-k+1>q.front()) q.pop_front();
			while(q.size()&&dp[q.back()]>dp[i]) q.pop_back();
			q.push_back(i);
		}
	}
	
	last[n+1]=0;
	a[n+1]=0;
	deque<int>qq;
	qq.push_back(n+1);
	for(int i=n;i>=1;i--){
		last[i]=last[qq.front()]+a[i];
		if(s[i]=='1'){
			qq.clear();
			qq.push_back(i);
		}
		else{
			if(qq.size()&&i+k-1<qq.front()) qq.pop_front();
			while(qq.size()&&last[qq.back()]>last[i]) qq.pop_back();
			qq.push_back(i);
		}
	}
}
void solve() {
	cin>>n>>k;
	for(int i=1;i<=n;i++) cin>>a[i];
	cin>>s;
	s=' '+s;
	init();
	cin>>Q;
	while(Q--){
		int p,v;
		cin>>p>>v;
		deque<int>q;
		for(int i=max(0ll,p-k);i<=p-1;i++){
			if(s[i]=='1'){
				q.clear();
				q.push_back(i);
			}
			else{
				if(q.size()&&i-k+1>q.front()) q.pop_front();
				while(q.size()&&dp[q.back()]>dp[i]) q.pop_back();
				q.push_back(i);
			}
		}
		for(int i=p;i<=min(n+1,p+k-1);i++) tmp[i]=dp[i];
		int ans=1e18;
		for(int i=p;i<=min(n+1,p+k-1);i++){
			if(i==p) dp[i]=dp[q.front()]+v;
			else dp[i]=dp[q.front()]+a[i];
			if(s[i]=='1'){
				q.clear();
				q.push_back(i);
			}
			else{
				if(q.size()&&i-k+1>q.front()) q.pop_front();
				while(q.size()&&dp[q.back()]>dp[i]) q.pop_back();
				q.push_back(i);
			}
			ans=min(ans,dp[i]+last[i]-a[i]);
		}
		cout<<ans<<endl;
		for(int i=p;i<=min(n+1,p+k-1);i++) dp[i]=tmp[i];
	}
}
signed main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	int t=1;
    cin>>t;
	while(t--) {
		solve();
	}
	return 0;
}