我觉得我的代码还是比较美观的

8.1 枚举和模拟

NOIP2001-J-2-最大公约数和最小公倍数问题

CPP

#include<bits/stdc++.h>
#define int long long
using namespace std;
int x,y,ans;
signed main(){
	scanf("%lld%lld",&x,&y);
	for(int i=1;i<=sqrt(x*y);i++){
		if(x*y%i) continue;
		if(__gcd(i,x*y/i)==x){
			ans+=2;//两数可以交换顺序
		} 
	}
	printf("%lld",ans);
	return 0;
}

本题需要根据一个等式不断推，由于C++自带一个__gcd()(最大公约数)函数，想求 $lcn$ （最小公倍数）就需要等式，即 $x \times y \div gcd(x,y)=lcn(x,y)$ ，将其变形可得 $lcn(x,y) \times gcd(x,y) = x \times y$ ，所以我们从1到 $\sqrt {x \times y}$ 枚举 $i$ ，然后判断 $x \times y$ 是否能整除 $i$ ，若能整除，那么另一个数就是 $x \times y \div i$ ，判断两个数的 $gcd$ 是否是 $x$ ，若是则答案数加二，因为两个数可以交换顺序，最后输出 $answer$ 即可，时间复杂度 $O(\sqrt{x \times y} )$

小信数矩形

CPP

#include<bits/stdc++.h>
using namespace std;
int n,ans;
struct node{
	int x,y;
}a[2005];
map <pair<int,int> ,int> m;
bool cmp(node x,node y){//不加排序过不了，好像是
	if(x.x==y.x)return x.y<y.y;
	return x.x<y.x;
} 
int main(){
	scanf("%d",&n);
	for(int i=1;i<=n;i++){
		scanf("%d%d",&a[i].x,&a[i].y);
		m[{a[i].x,a[i].y}]=1;
	}
	sort(a+1,a+n+1,cmp);
	for(int i=1;i<=n;i++){//左上角 
		for(int j=i+1;j<=n;j++){//右下角 
			if(a[i].x==a[j].x||a[i].y>=a[j].y) continue;//这里是必须有的，即判定是否是我选定类型的对角线（左上角和右下角形成的的对角线）
			if(m[{a[i].x,a[j].y}]==1&&m[{a[j].x,a[i].y}]==1) ans++;
		}
	}
	printf("%d",ans);
	return 0;
}

题目需要的是矩形的数量，我们可以直接枚举四个点，判断是否能形成矩形，但时间复杂度是很高的 $O( n^4 )$ ,所以我们需要优化矩形其实只需要一组对角线就能确定坐标，剩下的只需要判断另一组对角线上的点是否存在即可，这里我选择的是枚举左上角和右下角形成的对角线，在判断另两点是否存在之前，需先判断当前两点形成的对角线是否符合我们所选的类型，若两点都符合 $answer$ 加一，最后输出即可

矩形最大和

CPP

#include<bits/stdc++.h>
#define int long long
using namespace std;
int n,m,k,a[305][305],ans=-0x7fffffff;
int f[305][305][305];//列 起始行 终止行 
signed main(){
	scanf("%lld%lld%lld",&n,&m,&k);
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			scanf("%lld",&a[i][j]);
		}
	}
	for(int i=1;i<=m;i++){//列 
		for(int begin=1;begin<=n;begin++){//起始行 
			f[i][begin][begin]=a[begin][i];
			for(int end=begin+1;end<=n;end++){//终止行 
				f[i][begin][end]=f[i][begin][end-1]+a[end][i]; 
			}
		}
	}
	for(int begin=1;begin<=n;begin++){
		for(int end=begin;end<=n;end++){
			multiset <int> s;
			int x=0;
			for(int i=1;i<=m;i++){
				s.insert(f[i][begin][end]+x);
				x+=f[i][begin][end];
			}
			int d=0;
			auto it1=s.upper_bound(k);
            if(it1==s.begin()){
			}
			else{
				it1--;
				ans=max(ans,*it1);
			}
			for(int l=2;l<=m;l++){
				d+=f[l-1][begin][end];
				s.erase(s.find(d));
				auto it=s.upper_bound(k+d);
                if(it==s.begin()){
				}
				else{
					it--;
					ans=max(ans,*it-d);
				}
			}
		}
	}
	printf("%lld",ans);
	return 0;
}

~~十年oi一场空，不开longlong见祖宗~~
这道题有点像123第一场队内赛的第五题，所以我做题时想到三维状态比较简单，具体当时怎么讲的忘了，回去问问LilyDra， $f_{i,j,k}$ 的含义很简单，从第 $i$ 行到第 $j$ 行、第 $k$ 列的“上缀和”（把一维前缀和从上到下算，转个方向）,题目说, $a_{i,j}$ 有负数，所以不能用双指针。枚举开始行和结束行，在其中再算一个前缀和放到一个multiset里(不能去重）,列第一次从 $i=1$ 开始，把 $f_{1,begin,end},f_{1,begin,end}+f_{2,begin,end},f_{1,begin,end}+f_{2,begin,end}+f_{3,begin,end}……f_{1,begin,end}+f_{2,begin,end}……+f_{m-1,begin,end}+f_{m,begin,end}$ 放进去，用二分找最大不大于 $k$ 的值（upper_bound(）的指针减一），用 $anwser$ 存一下，再将 $i$ 向右移，这时就会有一个问题，我们需要把multiset里的值都减去 $f_{i,begin,end}$ ，但遍历减会超时，需再维护一个变量，维护当前应该减去的值（ $d$ ），所以multiset里的值是虚假的，真实值应减去 $d$ ，所以在二分时应二分（ $d+k$ ）， $i$ 右移时将假值是 $d$ 这一项删除。最后输出 $answer$ 即可，时间复杂度 $O(n^3 \log n)$

Symmetric Mountains

CPP

#include<bits/stdc++.h> 
using namespace std;
int n;
int a[5005];
int f[5005][5005];
int main(){
	scanf("%d",&n);
	for(int i=1;i<=n;i++){
		scanf("%d",&a[i]);
	}
	printf("0 ");//当截取长度是1时，最小不对称性时0
	for(int len=2;len<=n;len++){//枚举截取长度
		int ans=0x7fffffff;
		for(int l=1;l+len-1<=n;l++){//枚举左端点
			int r=l+len-1;//右端点
			f[l][r]=f[l+1][r-1]+abs(a[r]-a[l]);
			ans=min(ans,f[l][r]);
		} 
		printf("%d ",ans);
	}
	return 0;
}

这道题有两种做法，老师给的PPT上用的是双指针+枚举中点，这里就不说了。其实这道题从需要枚举截取的长度就可以猜想出时一个区间dp， $f_{l,r}$ 的含义是从 $a_l$ 截到 $a_r$ 的不对称性（没有最小！），那么 $f_{l,r}$ 是由 $f_{l-1,r-1}$ 推来，推导出状态转移公式， $f_{l,r}=f_{l-1,r-1}+abs(a_l-a_r)$ ，然后取 $min$ 输出即可，时间复杂度 $O(n^2)$

NOIP2014-S-DAY1-1-生活大爆炸版石头剪刀布

CPP

#include<bits/stdc++.h> 
using namespace std;
int n,x,y;
int a[205],b[205];
int ans1,ans2;
int main(){
	freopen("rps.in","r",stdin);
	freopen("rps.out","w",stdout);
	scanf("%d%d%d",&n,&x,&y);
	for(int i=1;i<=x;i++){
		scanf("%d",&a[i]);
	}
	for(int i=1;i<=y;i++){
		scanf("%d",&b[i]);
	}
	int l=1,r=1;
	while(n--){
		if(l==x+1) l=1;
		if(r==y+1) r=1;
		if(a[l]==b[r]){
		}
		else if(a[l]==0){
			if(b[r]==1) ans2++;
			else if(b[r]==2) ans1++;
			else if(b[r]==3) ans1++;
			else ans2++;
		}
		else if(a[l]==1){
			if(b[r]==0) ans1++;
			else if(b[r]==2) ans2++;
			else if(b[r]==3) ans1++;
			else ans2++;
		}
		else if(a[l]==2){
			if(b[r]==0) ans2++;
			else if(b[r]==1) ans1++;
			else if(b[r]==3) ans2++;
			else ans1++;
		}
		else if(a[l]==3){
			if(b[r]==0) ans2++;
			else if(b[r]==1) ans2++;
			else if(b[r]==2) ans1++;
			else ans1++;
		}
		else{
			if(b[r]==0) ans1++;
			else if(b[r]==1) ans1++;
			else if(b[r]==2) ans2++;
			else ans2++;
		}
		l++;
		r++;
	}
	printf("%d %d",ans1,ans2);
	return 0;
}

要开文件读写！
这个真么啥好说的，if屎山即可

CSP2023-J-3- 一元二次方程

CPP

#include<bits/stdc++.h>
#define int long long 
using namespace std;
int t,m;
signed main(){
	freopen("uqe.in","r",stdin);
	freopen("uqe.out","w",stdout);
	scanf("%lld%lld",&t,&m);
	while(t--){
		int a,b,c;
		scanf("%lld%lld%lld",&a,&b,&c);
		int delta=b*b-4*a*c;
		if(delta<0){//无解 
			printf("NO\n");
			continue;
		}
		else if(delta==0){//单个解 
			int temp=__gcd(2*a,-b);
			int mu=2*a/temp;
			int zi=-b/temp;
			if(mu<0){//分母不能有负号，转移至分子 
				mu*=(-1);
				zi*=(-1);
			}
			if(mu==1) printf("%lld\n",zi);//确保分母是1时不显示 
			else printf("%lld/%lld\n",zi,mu);
		}
		else{//
			int mu=2*a;
			int zi=-b;
			int z=1;	
			for(int i=2;i*i<=delta;i++){//化简根号 
				while(delta%(i*i)==0){
					z*=i;
					delta/=(i*i);
				}
			}
			if(delta==1){//根号1不出现 
				if(a>0){
					zi+=z;
				}
				else zi-=z;
				int temp=__gcd(zi,mu); 
				zi/=temp;
				mu/=temp;
				if(mu<0){
					mu*=(-1);
					zi*=(-1);
				} 
				if(mu==1) printf("%lld\n",zi);//确保分母是1时不显示 
				else printf("%lld/%lld\n",zi,mu);
			}
			else{//分两部分  -b/2a+-p*sqrt(q)/2a 
				int temp=__gcd(zi,mu);
				zi/=temp;
				mu/=temp;
				if(mu<0){
					mu*=(-1);
					zi*=(-1);
				} 
				if(mu==1&&zi){
					printf("%lld",zi);
				}
				else if(zi){
					printf("%lld/%lld",zi,mu);
				}
				if(zi){
					printf("+");
				} 
				if(a>0) zi=z;
				else zi=-z;
				mu=2*a;
				temp=__gcd(zi,mu);
				zi/=temp;
				mu/=temp;
				if(mu<0){
					mu*=(-1);
				} 
				if(mu==1){
					if(zi==1){
						printf("sqrt(%lld)\n",delta);
					}
					else{
						printf("%lld*sqrt(%lld)\n",zi,delta);
					}
				}
				else{
					if(zi==1){
						printf("sqrt(%lld)/%lld\n",delta,mu);
					}
					else{
						printf("%lld*sqrt(%lld)/%lld\n",zi,delta,mu);
					}
				}
			}
		}
	}
	return 0;
}

~~这个题是真恶心啊~~
纯模拟，没有任何高深算法，只有分数在化简的时候用到了__gcd()

CSP2020-S-1-儒略日(非AC代码)

CPP

#include<bits/stdc++.h> 
#define int long long
using namespace std;
int t,m,year,r;
int leap(int y){
	if(y<1582){
		return y%4==0;
	}
	if(y%400==0){
		return 1;
	}
	if(y%100==0){
		return 0;
	}
	return y%4==0;
}
signed main(){
    freopen("julian.in","r",stdin);
    freopen("julian.out","w",stdout);
	scanf("%lld",&t);
	while(t--){
		scanf("%lld",&r);
		if (r<2299161){//在 1582年10月4日及以前 
			int r1=r/1461;//3平+1闰（一组）=1461天 
			 r-=r1*1461;
			if (r<366){
				year=r1*4-4712;
			}
			else if(r<731){
				year=r1*4-4711;
				r -= 366;
			}
			else if(r<1096){
				year=r1*4-4710;
				r-=731;
			}
			else{
				year=r1*4-4709;
				r-=1096;
			}
		}
		else{//第n周期第d天的儒略日就是2159351+d+n*146097
			int r2=(r-=2159351)/146097;
			r-=r2*146097;
			year=1200+r2*400;
			r2=(r-1)/36524;
			r-=r2*36524;
			year+=r2*100;
			r2=r/1461;
			r-=r2*1461;
			year+=r2 * 4;
			if (r<366){
				if (!leap(year)){
					--r;
				}
			}
			else if(r<731 ){
				++year;
				r-=366;
			}
			else if(r < 1096){
				year+=2;
				r-=731;
			}
			else{
				year+=3;
				r-=1096;
			}
			if(leap(year)){
					if(r<31) m=1;
					else if(r<60) m=2,r-=31;
					else if(r<91) m=3,r-=60;
					else if(r<121) m=4,r-=91;
					else if(r<152) m=5,r-=121;
					else if(r<182) m=6,r-=152;
					else if(r<213) m=7,r-=182;
					else if(r<244) m=8,r-=213;
					else if(r<274) m=9,r-=244;
					else if(r<305) m=10,r-=274;
					else if(r<335) m=11,r-=305;
					else m=12,r-=335;
			}
			else{
				if(r<31) m=1;
				else if(r<59) m=2,r-=31;
				else if(r<90) m=3,r-=59;
				else if(r<120) m=4,r-=90;
				else if(r<151) m=5,r-=120;
				else if(r<181) m=6,r-=151;
				else if(r<212) m=7,r-=181;
				else if(r<243) m=8,r-=212;
				else if(r<273) m=9,r-=243;
				else if(r<304) m=10,r-=273;
				else if(r<334) m=11,r-=304;
				else m=12,r-=334;
				}
		}
		int day=r+1;
		if(year>0){
			printf("%lld %lld %lld\n",day,m,year);
		}
		else{
			printf("%lld %lld %lld BC\n",day,m,1-year);
		}
	}
	return 0;
}

~~这题比上道题还™恶心~~

8.2模考

张的弓

CPP

#include<bits/stdc++.h>
#define int long long
using namespace std;
int t;
int n,m,k,ans;
signed main(){
	scanf("%lld",&t);
	while(t--){
		scanf("%lld%lld%lld",&n,&m,&k);
		if(k==n){
			printf("%lld\n",n);
			continue;
		}
		int up=k/n;
		int com=k-up;
		if(up%2==1){
			if(com%(n-1)==0){
				if(up==com/(n-1)){
					printf("%lld\n",up+n-1);
				}
				else{
					printf("%lld\n",up);
				}
			}
			else{
				com%=(n-1);
				int x=n-com;
				printf("%lld\n",up+x-1);
			}
		}
		else{
			if(com%(n-1)==0){
				if(up==com/(n-1)){
					printf("%lld\n",up);
				}
				else{
					printf("%lld\n",up+n-1);
				}
			}
			else{
				com%=(n-1);
				printf("%lld\n",up+com);
			}
		} 
	} 
	return 0;
}

$n,m$ 不要输入反了！
这道题纯模拟，看过数据范围知道，不能dfs模拟，所以我们就if屎山

绝对公平

CPP

#include<bits/stdc++.h>
using namespace std;
vector <int> pri;//质数 
int t,a[100005];
int main(){
	for(int i=2;i<=1e6;i++){
		bool fl=1;
		for(int j=2;j<=sqrt(i);j++){
			if(i%j==0){
				fl=0;
				break;
			}
		}
		if(fl){
			pri.push_back(i);
		//	cerr<<i<<" ";
		}
	}
	scanf("%d",&t);
	while(t--){
		map <int,int> m;
		int n;
		scanf("%d",&n);
		for(int i=1;i<=n;i++){
			scanf("%d",&a[i]);
			for(int j=0;pri[j]<=a[i]&&a[i]!=1;j++){
				while(a[i]%pri[j]==0){
					a[i]/=pri[j];
					m[pri[j]]++;
				}
			}
//			if(a[i]!=1){
//				m[a[i]]++;
//			}
		}
		bool flag=1;
		for(auto it:m){
			if(it.second%n){
				flag=0;
				printf("NO\n");
				break;
			}
			if(flag==0) break; 
		}
		if(flag){
			printf("YES\n");
		}
	}
	return 0;
}

考试的时候把这道题想简单了
这道题应该把所有数分解质因数（有分解因数想到分解质因数），然后看所有一个类型的质因数个数能否均分即可

AI作曲

CPP

#include<bits/stdc++.h>
using namespace std;
int t,f[105][55],a[105],b[55][55];
int n,m;
int main(){
	scanf("%d",&t);
	while(t--){
		memset(f,0,sizeof(f));
		scanf("%d%d",&n,&m);
		for(int i=1;i<=m;i++){
			for(int j=1;j<=m;j++){
				scanf("%d",&b[i][j]);
			}
		}
		for(int i=1;i<=n;i++){
			scanf("%d",&a[i]);
		}
		for(int i=2;i<=n;i++){
			int l=1,r=m;
			if(a[i]!=-1) l=a[i],r=l;
			for(int j=l;j<=r;j++){
				int x=1,y=m;
				if(a[i-1]!=-1) x=a[i-1],y=x;
				for(int k=x;k<=y;k++){
					f[i][j]=max(f[i][j],f[i-1][k]+b[k][j]);
				}
			}
		}
		int ans=-0x7fffffff;
		for(int i=1;i<=m;i++){
			ans=max(ans,f[n][i]);
		}
		printf("%d\n",ans);
	}

	return 0;
}

这道题考试的时候看出来了，但真没敢想写dp，其实还挺简单的
我们先定义dp的状态含义，即 $f{i,j}$ 表示到第 $i$ 个点,且第 $i$ 个点填音符类型为 $j$ 的最大音乐美度。
由上图可知我们的转移路线，但上图仅适用于可以随便填的情况（即 $a_i = -1$ ），然后就可以推出一个可以随便填的状态转移公式，即 $f_{i,j}$ ，而数据给定音符时，就将其他状态初始化为极小值，不让其他不合法状态转移出去，或者让 $j$ 和 $k$ 只走合法状态

小信的特工行动

CPP

#include<bits/stdc++.h>
#define int unsigned long long
using namespace std;
int n;
int a[50],S;
int sum;
string s1;
unordered_map <int,string> m;
void dfs1(int id){
	
	if(id>n/2){
		m[sum]=s1;
		return ;
	} 
	sum+=a[id];
	s1[id-1]='1';
	dfs1(id+1);
	sum-=a[id];
	s1[id-1]='0';
	dfs1(id+1);
	return ;
}
int num;
string s2;
void dfs2(int id){
	if(id>n){
		if(m.count(S-num)){
			cout<<m[S-num]<<s2;
		}
		return ;
	} 
	s2[id-1-n/2]='1';
	num+=a[id];
	dfs2(id+1);
	s2[id-1-n/2]='0';
	num-=a[id];
	dfs2(id+1);
	return ;
}
signed main(){
	scanf("%llu",&n);
	for(int i=1;i<=n;i++){
	}
	
	for(int i=1;i<=n/2;i++){
		s1+="0";
	}
	for(int i=n/2+1;i<=n;i++){
		s2+="0";
	}
	scanf("%llu",&S);
	dfs1(1);
	dfs2(n/2+1);
	
	return 0;
}

这是我做的第一道折半搜索，~~真™恶心~~
这道题在考试的时候我是根本没读懂题，题面全是废话，老师言：诈骗
这道题其实就是从 $n$ 个数里选，要组成 $s$ ，然后输出每个数选不选，很明显的搜索，但仔细看 $n$ 的数据范围 $1 \le n \le 45？！$ （众所周知搜索的时间复杂度是 $O(2^n)$ ，程序大约1秒跑 $2^{26}$ 左右），假如 $n$ 能变成一半就好了，这时候，伟大的折半搜索就出面了，即从左边搜一半，从右边搜一半，最后把答案合起来输出即可
这里注意， $dfs$ 的参数是放在一个栈里的，而这道题我们需要记字符串，它需要的空间是很大的，这就会造成栈溢出（RE）,所以要把字符串建立在全局里

8.3贪心

距离相等的条形码

CPP

#include<bits/stdc++.h>
using namespace std;
int n;
map <int,int> m;
vector <int> v;
priority_queue<pair<int,int> > q;
int main(){
	scanf("%d",&n);
	for(int i=1;i<=n;i++){
		int x;
		scanf("%d",&x);
		m[x]++;
	}
	for(auto i:m){
		q.push({i.second,i.first});
	}
	int last=-1;
	while(!q.empty()){
		auto u=q.top();
		q.pop();
		if(u.second==last){
			auto t=q.top();
			q.pop();
			t.first--;
			last=t.second;
			v.push_back(last);
			if(u.first)q.push(u);
			if(t.first)q.push(t);
		}
		else{
			last=u.second;
			v.push_back(last);
			u.first--;
			if(u.first)q.push(u);
		}
	}
	for(int i:v){
		printf("%d ",i);
	}
	return 0;
}

这道题贪心在优先放剩下个数最多的数，就按照个数从大到小放在大顶堆里，如果上一个也是当前取出的这个数，那么就放第二多的，以此类推，放完输出

打水

CPP

#include<bits/stdc++.h>
using namespace std;
double n,ans;
struct node{
	int id,val;
}a[10005];
bool cmp(node x,node y){
	if(x.val==y.val) return x.id<y.id;
	return x.val<y.val;
}
int main(){
	scanf("%lf",&n);
	for(int i=1;i<=n;i++){
		scanf("%d",&a[i].val);
		a[i].id=i;
	}
	sort(a+1,a+(int)n+1,cmp);
	int sum=0;
	for(int i=1;i<=n;i++){
		ans+=sum;
		sum+=a[i].val;
		printf("%d ",a[i].id);
	}
	printf("\n%.2lf",ans*1.0/n*1.0);
	return 0;
}

一道非常非常经典的贪心，唯一可说的就是 $n$ 和 $sum$ 要开 double……（血的教训），否则会WA on #2

删数问题

CPP

#include<bits/stdc++.h>
using namespace std;
int n;
string s;
int l;
int main(){
	cin>>s>>n;
	l=s.size();
	while(n--){
		for(int i=0;i<l;i++){
			if(i==s.size()-1){
				for(int j=i;j<l;j++) s[j]=s[j+1];
				l--;
				break;
			}
			if(s[i]>s[i+1]){
				for(int j=i;j<l;j++) s[j]=s[j+1];
				l--;
				break;
			}
		}
		//cerr<<s;
	}
	int be=0;
	for(int i=0;i<l;i++){
		if(s[i]=='0') be++;
		else break;
	}
	if(s.substr(be,l-be)==""){
		printf("0");
		return 0;
	}
	cout<<s.substr(be,l-be);
	return 0;
}

这道题需要找规律，通过老湿带我们模样例得出结论，若 $s_i>s_{i+1}$ ，那么就删掉 $a_i$ ，然后重新遍历，若没有这样的 $s_i$ ，那就删除最后一项。

过河问题

CPP

#include<bits/stdc++.h>
#define int long long
using namespace std;
int n,ans;
int a[100006];
signed main(){
	scanf("%lld",&n);
	for(int i=1;i<=n;i++){
		scanf("%lld",&a[i]);
	}
	sort(a+1,a+n+1);
	while(n>3){
		ans+=min(a[1]*2+a[n]+a[n-1],a[1]+a[2]*2+a[n]);
		n-=2;
	}
	if(n==3){
		ans+=a[3];
		ans+=a[1];
		ans+=a[2];
	}
	else{
		ans+=a[2];
	}
	printf("%lld",ans);
	return 0;
}

假设共有4个人（即样例），他们过河所花时间分别是 $1,2,5,10$ （即样例），有以下几个思想（求最短过河时间）：
思想一：每次选择当前过河速度最快的两人。首先1和2过河，1把船开回，共耗时2+1=3；1和5过河，1把船开回，总时间变为3+5+1=9,；最后一趟1和10过河，总时间变成9+10=19
思想二：每次选择过河速度最慢的两人…………（懒得写了bushi）总耗时24
思想三：每次选过河最快和最慢的两人…………总时间是19
思想四：每次选最快的两人过河，然后让最慢的两人过河
不难发现，没送到对岸两人需要来回两次，猜想三的时间是 $a_1+a_1+a_k+a_{k-1}$ 而猜想四的时间是 $a_1+a_2+a_2+a+k$ ，我们无法确定那个时间短，所以取 $min$ 即可，当我们还有3人在左岸时，总耗时还需要加 $a_3+a_1+a_2$ ，当我们剩余两人在左岸时，总时间要加 $a_2$ 。最后输出即可

Maximum AND

CPP

#include<bits/stdc++.h>
using namespace std;
int n,ans;
int a[100005];
int b[100005];
bool _(int x){
	vector <int> v,u;
	for(int i=1;i<=n;i++){
		u.push_back(a[i]&x);
		v.push_back((b[i]&x)^x); 
	}
	sort(v.begin(),v.end());
	sort(u.begin(),u.end());
	return u==v;
} 
int main(){
	scanf("%d",&n);
	for(int i=1;i<=n;i++){
		scanf("%d",&a[i]);
	}
	for(int i=1;i<=n;i++){
		scanf("%d",&b[i]);
	}
	for(int i=29;i>=0;i--){
		if(_(ans|(1<<i))){
			ans|=(1<<i);
		}
	}
	printf("%d",ans);
	return 0;
}

~~这道题真没大理解，下边都是豆包写的~~

这道题的关键在于贪心算法与位运算的结合：
二进制数的高位对数值大小的影响远大于低位，因此我们应优先确定高位
从最高位（如第 29 位，因为 $a_i$ < $2^{30}$ ）开始，尝试确定每一位是否可以为 1
对于每一位，我们检查是否存在一种排列方式，使得所有 $c_i$ 的当前位及已确定的高位都能保持为 1

Treasure Hunt

CPP

#include<bits/stdc++.h>
using namespace std;
int n,an,bn,cn;
map <char,int> m;
string a,b,c;
int main(){
	cin>>n>>a>>b>>c;
	for(auto i:a){
		m[i]++;
		an=max(an,m[i]);
	}
	m.clear();
	for(auto i:b){
		m[i]++;
		bn=max(bn,m[i]);
	}
	m.clear();
	for(auto i:c){
		m[i]++;
		cn=max(cn,m[i]);
	}
	an=min(an+n,(int)a.size());
	bn=min(bn+n,(int)b.size());
	cn=min(cn+n,(int)c.size());
	if(an>bn&&an>cn){
		printf("Kuro");
	}
	else if(bn>cn&&bn>an){
		printf("Shiro");
	}
	else if(cn>bn&&cn>an){
		printf("Katie");
	}
	else{
		printf("Draw");
	}
	return 0;
}

这道题共有两步推出最大美丽值
以字符串abcabca为例，其中abc出现两次，ab(bc,ca,b,c)出现两次，a出现三次。由此推出子串长度越小，出现越大，所以我们只需统计每个字符的个数即可
以字符串aba为例，我们修改一次，最大美丽值是3（aaa），即把b改成a；修改两次呢，有的同学可能会说“2”，但其实还是3，可以先把b改成其他字符，再把其他字符改成a以此类推……
其实这里还有一种情况，就是aaa改一次，那么答案就是2，但牢实说题目数据太水了，没有这样的数据，~~建议加强~~
由上面可以推出答案，即出现最多字符的个数+修改次数与字符串长度取 $min$ 即可

泡泡堂

CPP

#include<bits/stdc++.h>
using namespace std;
int n,a[1000005],b[1000005];
int best,lss;
int main(){
	scanf("%d",&n);
	for(int i=1;i<=n;i++){
		scanf("%d",&a[i]); 
	}
	for(int i=1;i<=n;i++){
		scanf("%d",&b[i]);
	} 
	sort(a+1,a+n+1);
	sort(b+1,b+n+1);
	int l=1,r=n;
	int x=1,y=n;
	while(l<=r&&x<=y){
		if(a[l]>b[x]){
			l++;
			x++;
			best+=2;
			
		}
		else if(a[r]>b[y]){
			r--;
			y--;
			best+=2;
			cerr<<2;
		}
		else if(a[l]==b[y]){
			y--;
			l++;
			best++;
		}
		else{
			l++;
			y--;
		}
	}
	l=1,r=n;
	x=1,y=n;
	while(l<=r&&x<=y){
		if(b[l]>a[x]){
			l++;
			x++;
		}
		else if(b[r]>a[y]){
			r--;
			y--;
		}
		else if(b[l]==a[y]){
			y--;
			l++;
			lss++;
		}
		else{
			l++;
			y--;
			lss+=2;
		}
	}
	printf("%d %d",best,lss);
	return 0;
}

其实这道题就是一个两边的田忌赛马
我方得分最多就是对方得分最少
如果我最差的选手能赢对手最差的选手那就赢
如果我最好的选手能赢对手最好的选手那就赢
如果我最差的选手能平对手最好的选手那就平
如果我最好的选手赢不了对手最好的选手，那就用最差的选手输
综上所述，我们可以得出最优策略，且用两个双指针维护目前最好的选手位置和最差选手的位置，正反各一遍即可

8.4模考

比较数字

CPP

#include<bits/stdc++.h>
using namespace std;
string s;
int main(){
	freopen("A.in","r",stdin); 
	freopen("A.out","w",stdout);
	cin>>s;
	int len=s.size();
	bool fl=1;
	for(int i=0;i<len;i++){//n有0 
		if(fl==0){
			s[i]='1';
		}
		else if(s[i]=='0'){
			fl=0;
			s[i]='1';
		}
	}
    cout<<s;
    return 0;

这道题一开始我以为是把这个数加上1，然后处理进位，把所有0变成1,但老师给了大样例，才发现是遇到第一个0就把后面的数全变成1，还有文件读写

修剪灌木

CPP

#include<bits/stdc++.h>
using namespace std;
int n,k,a[2000050],ans,mn=0x7ffffff;
int main(){
	scanf("%d%d",&n,&k);
	for(int i=1;i<=n;i++){
		scanf("%d",&a[i]);
	}
	sort(a+1,a+n+1);
	map <int,pair<int,int> > m;//当前数的个数，共经过几次操作 
	for(int i=1;i<=n;i++){
		int u=a[i];
		int j=0;//经过j次操作 
		while(u){
			m[u].second+=j;
			m[u].first++;
			if(m[u].first>=k){
				mn=min(mn,m[u].second);
			}
			u/=2;
			j++;
		}
	} 
	printf("%d",mn);
	return 0;
}

~~这道题我自作聪明的写了二分答案，以为是正解~~
其实这道题我大致思路是对的，就是把 $a_i$ 不断除以2，标记这个数需要的步数，最后取 $min$ 即可

最小成本

CPP

#include<bits/stdc++.h>
#define int long long
using namespace std;
int k,n,m,a[205][205],f[205][205][205],x[205][205];
int t;
const int inf=0x3f3f3f3f3f3f3f3f;
signed main(){
    freopen("D.in","r",stdin);
    freopen("D.out","w",stdout);
	scanf("%lld",&t);
	while(t--){
		scanf("%lld%lld%lld",&n,&m,&k);
		for(int i=1;i<=n;i++){
			for(int j=1;j<=m;j++){
				x[i][0]=inf;
				x[0][j]=inf;
				x[i][j]=inf;
				for(int q=0;q<=m;q++){	
					f[i][j][q]=inf;	
					f[0][j][q]=inf;
					f[i][0][q]=inf;
				} 
				scanf("%lld",&a[i][j]);
			}
		}
		x[0][1]=x[1][0]=0;

		for(int i=1;i<=n;i++){
			for(int j=1;j<=m;j++){
				for(int q=0;q<m;q++){
					int tt=j+q;
					if(tt>m)tt-=m;
					f[i][j][q]=min({f[i][j][q] ,x[i-1][j]+a[i][tt]+q*k,f[i][j-1][q]+a[i][tt]});
					x[i][j]=min(f[i][j][q],x[i][j]);
				}
			}
		}

		printf("%lld\n",x[n][m]);
	}
	return 0;
}

非常明显的dp，考试没写出来正解aaa ~~(不过确实不太好写)~~
这道题需要一个三维状态， $f_{i,j,k}$ 表示第 $i$ 行、第 $j$ 列、转动 $k$ 次的最小值，因此我们需要枚举第三层 $q$ 来表示这一行的旋转次数，可以推出状态转移公式， $f_{i,j,q}=min({f_{i,j,q} ,f_{i,j,qq(这个地方需要枚举上一行的旋转次数)}+a_{i,(j+q-1) \mod m+1}+q \times k,f_{i,j-1,q}+a_{i,(j+q-1) \mod m+1}})$ ，然后就会发现，四层循环过不了啊，我们要的是上一行 $min(f_{i,j,q=1,2,3……m-2,m-1})$ 所以我们可以找个数组存 $min(f_{i,j,q=1,2,3……m-2,m-1})$ 记为 $x_{i,j}$ 所以状态转移公式就会变成 $f_{i,j,q}=min({f_{i,j,q} ,x_{i,j}+a_{i,(j+q-1) \mod m+1}+q \times k,f_{i,j-1,q}+a_{i,(j+q-1) \mod m+1}})$ ，最后输出 $x_{n,m}$ 即可

论坛大师

这道题如果想写最优的话，需要stl全家桶

CPP

#include<bits/stdc++.h>
using namespace std;
int t,n;
vector <int> v;
map<int,int> m;
int top=-1;
int main(){
	scanf("%d",&t);
	while(t--){
		v.clear();
		m.clear();
		top=-1;//初始化 
		scanf("%d",&n);
		for(int i=1;i<=n;i++){
			
			string s;
			cin>>s;
			printf("Operation #%d: ",i);
			if(s=="Add"){
				int u;
				scanf("%d",&u);
				if(m.count(u)){
					printf("same priority");
				}
				else{
					m[u]=0;
					v.push_back(u);
					printf("success");
				}
			}
			else if(s=="Close"){
				int u;
				scanf("%d",&u);
				if(!m.count(u)){
					printf("invalid priority");
				}
				else{
					printf("close %d with %d",u,m[u]);
					m.erase(u);
					v.erase(find(v.begin(),v.end(),u));
				}
			}
			else if(s=="Chat"){//
				int w;
				scanf("%d",&w);
				if(v.empty()){
					printf("empty"); 
				}
				else if(top!=-1&&m.count(top)){
					m[top]+=w;
					printf("success");
				}
				else{
					m[v[0]]+=w;
					printf("success");
				}
			} 
			else if(s=="Rotate"){
				int x;
				scanf("%d",&x);
				if(x>v.size()){
					printf("out of range");
				}
				else{
					int un=v[x-1];
					v.erase(v.begin()+x-1);
					v.insert(v.begin(),un);
					printf("success");
				}
			}
			else if(s=="Prior"){
				if(v.empty()){
					printf("empty");
				}
				else{
					int mx=0;
					int uu=v[mx]; 
					for(int j=0;j<v.size();j++){
						if(v[j]>v[mx]){
							mx=j;
							uu=v[mx];
						}
					}
					v.erase(v.begin()+mx);
					v.insert(v.begin(),uu);
					printf("success");
				}
			}
			else if(s=="Choose"){
				int u;
				scanf("%d",&u);
				if(m.count(u)){
					v.erase(find(v.begin(),v.end(),u));
					v.insert(v.begin(),u);
					printf("success");
				}
				else{
					printf("invalid priority");
				}
			}
			else if(s=="Top"){
				int u;
				scanf("%d",&u);
				if(m.count(u)){
					printf("success");
					top=u;
				}
				else{
					printf("invalid priority");
				}
			} 
			else{
				if(top==-1){
					printf("no such person");
				}
				else{
					top=-1;
					printf("success");
				}
			}
			 puts(".");
		}
		if(v.empty()){
		}
		else{
			if(top!=-1&&m.count(top)){//
				printf("Bye %d: %d\n",top,m[top]);
				v.erase(find(v.begin(),v.end(),top));
			}
			if(!v.empty()){
				for(auto i:v){
					if(i!=top&&m[i]) printf("Bye %d: %d\n",i,m[i]);
				}
			}
		}
	}
	return 0;
}

~~非AC代码~~
这道题就是纯模拟，没啥好说，用vector即可
find()函数用法：find(a.begin()数组开始的迭代器，a.end()数组结束的迭代器，s需要查找的值)，返回一个迭代器
动态数组insert：其实是插入v.insert(v.begin(),s)，先放插入的位置，后放插入的值或一些值

8.5线性技巧及数据结构

大哈贴广告

CPP

#include<bits/stdc++.h>
using namespace std;
int n,m;
int f[3005][3005],b[3005][3005];
int main(){
	scanf("%d%d",&n,&m);
	for(int i=1;i<=m;i++){
		int x,y,xx,yy;
		scanf("%d%d%d%d",&x,&y,&xx,&yy);
		f[x][y]++;
		f[x][yy+1]--;
		f[xx+1][y]--;
		f[xx+1][yy+1]++;
	}
	for(int i=1;i<=n;i++){
		for(int j=1;j<=n;j++){
			b[i][j]=b[i-1][j]+b[i][j-1]-b[i-1][j-1]+f[i][j];
			printf("%d ",b[i][j]);
		} 
		puts("");
	}
	return 0;
}

二维差分即可（这道题我一年前就过了）
二维差分是基于二维前缀和的思想，把 $f_{i,j}$ ~ $f_{x,y}$ 这个区间加上1，把 $f_{i,j}$ 加1、 $f_{i,y+1}$ 减去1、 $f_{x+1,j}$ 减去1,、把 $f_{x+1,y+1}$ 加1，最后二维前缀和复原即可

[202502E]小信的区间加法

CPP

#include<bits/stdc++.h>
#define int long long
using namespace std;
int n,m,a[2000005],b[2000005],c[2000005],f[3000005];
signed main(){
    freopen("202502E.in","r",stdin);
    freopen("202502E.out","w",stdout);
	scanf("%lld%lld",&n,&m);
	for(int i=1;i<=n;i++) scanf("%lld",&a[i]);
	for(int i=1;i<=m;i++){
		int l,r;
		scanf("%lld%lld",&l,&r);
		f[l]++;
		f[r+1]+=-1;
		f[r+1]-=(r-l+1);
		f[r+2]+=(r-l+1);
	}
	for(int i=1;i<=n;i++){
		b[i]=b[i-1]+f[i];
		c[i]=c[i-1]+b[i];
		printf("%lld ",c[i]+a[i]);
	}
	return 0;
}

要开文件读写！
这道题用普通差分是不行的，应为区间加上的不是一个值，但他加的是一个等差数列，所以我们需再用一个差分记这个差分的区间加，最后两遍前缀和复原

[202501C]BotGPT

CPP

#include<bits/stdc++.h>
using namespace std;
int n,m,k,a[3000005],b[3000005][2],ans;
int c[3000005];
bool fl;
int f[3000005];
bool check(int mid){
	int num=0;
	for(int i=1;i<=n;i++) c[i]=0,f[i]=0;
	for(int i=1;i<=mid;i++){
		c[b[i][0]]++;
		c[b[i][1]+1]--;
	}
	
	for(int i=1;i<=n;i++){
		f[i]=f[i-1]+c[i];
		if(f[i]>=a[i]) num++;
	}
	return num>=k;
}
int main(){
    freopen("202501C.in","r",stdin);
    freopen("202501C.out","w",stdout);
	scanf("%d%d%d",&n,&m,&k);
	for(int i=1;i<=n;i++){
		scanf("%d",&a[i]);
	}
	for(int i=1;i<=m;i++){
		scanf("%d%d",&b[i][0],&b[i][1]);
	}
	int l=1,r=m;
	while(l<=r){
		int mid=l+(r-l)/2;
		if(check(mid)){
			r=mid-1;
			fl=1;
			ans=mid;
		}
		else{
			l=mid+1; 
		}
	}
	if(fl==0){
		printf("%d",m);
        return 0;
	}
	printf("%d",ans);
	return 0;
}

通过把区间内加1，就可以判断是差分，但差分需要操作完成才能访问，而枚举打回第几版又会超时，所以我们想到二分，注意需要判断 $ans$ 如果改变过就输出，没有就输出 $m$

逛画展

CPP

#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<string>
#include<vector>
#include<algorithm>
#include<ctime>
#include<map>
#include<cstdlib>
#include<queue>
using namespace std;
int m,n,a[1000005],mx=0x7fffffff,x,y;
int main(){
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++){
		scanf("%d",&a[i]);
	}
	map<int,int> mp;
	int r=1,cnt=0;
	for(int l=1;l<=n;l++){
		while(r<=n&&cnt<m){
			mp[a[r]]++;
			if(mp[a[r]]==1) cnt++;
			r++;
		}
		if(mx>r-l&&cnt>=m){
			mx=r-l;
			y=r;
			x=l;
		}
		mp[a[l]]--;
		if(mp[a[l]]==0) cnt--;
	}
	printf("%d %d",x,y-1);
	return 0;
}

这道纯双指针，只需用 map记录是否包含1~n即可

Max Min

CPP

#include<bits/stdc++.h>
#define int long long
using namespace std;
int ans,n,x,y,idx=-1,idy=-1,a[2000005];
int l;//左边 
signed main(){
	scanf("%lld%lld%lld",&n,&x,&y);
	for(int i=1;i<=n;i++){
		scanf("%lld",&a[i]);
	}
	for(int i=1;i<=n+1;i++){
		if(a[i]==x){
			idx=max(i,idx);
		}
		 if(a[i]==y){
			idy=max(i,idy);
		}
		if(a[i]<=x&&a[i]>=y){
			if(idx!=-1&&idy!=-1) ans+=min(idx,idy)-l;
		}
		else{
			idx=-1;
			idy=-1;
			l=i;
		}
	}
	printf("%lld",ans);
	return 0;
}

因为是子串，他必须连续啊！所以我们可以考虑以每一个元素作为结尾时的方案，且这个方案中每个子串都需要包含最大和最小值，我们先考虑当 $a_i$ <y或 $a _i$ > $x$ 时，那必然是不能选进去的，所以我们就从开头或者是它的后面选，我们就可以统计下目前到这个元素的元素值是否包含 $x$ 或 $y$ ，如果都包含，那说明这个元素一定能作为子串的结尾，那我们只需要统计一下前面 $x$ 和 $y$ 出现的地方距离它的最远距离，如果出现了第二个 $x$ 或 $y$ 前面那个就当成普通元素就行了

8.6模考

小信数1

CPP

#include<bits/stdc++.h>
using namespace std;
int a,b,c;
int main(){
	scanf("%d%d%d",&a,&b,&c);
	printf("%d",2+(b-c-1));
	return 0;
}

本题是一个数学题，当你看到 $2^a$ 想要模拟时，会发现 $1 \le c < b < a \le 10^9$ 呵呵
我是通过自己出了一个样例，~~毕竟题目样例很多有误导性~~，拿 $a=5,b=4,c=2$ 来说吧，首先 $2^a+2^b$ 贡献了2个1，然后减去 $2^c$ 只会影响 $2^b$ 我们会发现，他俩相减出现了 $b-c$ 个1，但 $2^b$ 的1没有了，所以需要减去1

糖豆人派对

CPP

#include<bits/stdc++.h>
#define int long long
using namespace std;
int R,l,r,n;
int x;
signed main(){
	scanf("%lld%lld",&R,&n);
	r=R;
	for(int i=1;i<=n;i++){
		scanf("%lld",&x);
		if(x<0){
			l=max(l+x,0ll);
			r=max(r+x,0ll);
		}
		else{
			l=min(l+x,R);
			r=min(r+x,R);
		}
	}
	if(l==r){
		printf("%lld",r);
	}
	else printf("-1");
	return 0;
}

这道题考试的时候，cys信誓旦旦的说能过，结果……
这道题其实就是一个左边界表示最左边人所在位置，右边界表示最右边人所在位置
当向右移时， $l$ 和 $r$ 需要从 $l \ or \ r+x$ 和 $R$ （右边界）取 $min$
当向左移时， $l$ 和 $r$ 需要从 $l \ or \ r+x$ 和 $0$ （左边界）取 $max$
最后如果 $l$ 和 $r$ 相等，那么输出；否则输出-1

破译密码机

CPP

#include<bits/stdc++.h>
using namespace std;
int t,n,m;
bool flag=1;
vector <int> a,b;
void dfs(vector <int> v){

	if(v.size()<m){
		return ;
	} 

	if(v.size()==m){
		if(v==b){
			flag=0;
		}
		else{
			reverse(v.begin(),v.end());
			if(v==b) flag=0;
		}
		return ;
	}
	for(int d=0;d<v.size()-1;d++){//折叠点 
		int l=d,r=d+1;
		vector<int> u;
		while(l>=0&&r<v.size()){
			u.insert(u.begin(),v[r]+v[l]);
			l--;
			r++;
		}
		while(l>=0){
			u.insert(u.begin(),v[l]);
			l--;
		}
		while(r<v.size()){
			u.insert(u.begin(),v[r]);
			r++;
		}
		dfs(u);
	}
	return ;
}
signed main(){
	scanf("%d",&t);
	while(t--){
		a.clear();
		b.clear();
		 flag=1;//初始化 
		scanf("%d",&n);
		for(int i=1;i<=n;i++){
			int x;
			scanf("%d",&x);
			a.push_back(x);
		}
		scanf("%d",&m);
		for(int i=1;i<=m;i++){
			int x;
			scanf("%d",&x);
			b.push_back(x);
		}
		dfs(a);
		if(flag) printf("N\n"); 
		else printf("S\n");
	}
	return 0;
}

这道题开始的时候没看见可以折多次，要不然也是能挣一下
这道题就是不断搜索（从数据范围也能看出来好吧），然后找原字符串是否能变成目标字符串即可
原题上说可以翻转，但如果在搜索里加上翻转的话会死循环的，所以在最后判断时加一个翻转判断

补充题：编辑距离

CPP

#include<algorithm>
#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<queue>
#include<vector>
#include<stack>
#include<map>
#include<set>
#include<ctime>
#include<cstdlib>
//#include<cmath>
using namespace std;
string a,b;
int dp[5005][5005];
int main(){
	cin>>a>>b;
	int n=a.size(),m=b.size();
	for(int i=1;i<=n;i++){dp[i][0]=i;}
	for(int i=1;i<=m;i++){dp[0][i]=i;}
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			if(a[i-1]==b[j-1]){
				dp[i][j]=dp[i-1][j-1];
			}
			else{
				dp[i][j]=min({dp[i-1][j],dp[i][j-1],dp[i-1][j-1]})+1;
			}
		}
	} 
	printf("%d",dp[n][m]);
	return 0;
}

之前做过，~~鸣谢LilyDra~~
$f_{i,j}$ 的含义是 $a$ 的前 $i$ 个字符和 $b$ 的前 $j$ 个字符需要的最小操作次数
其实当 $a_i = b_i$ 时， $f_{i,j}=f_{i-1,j-1}$
当 $a_i \ne b_i$ 时， $f_{i,j}=min(f_{i-1,j}+1,f_{i,j-1}+1,f_{i-1,j-1}+1)$

最优匹配

CPP

#include<bits/stdc++.h>
using namespace std;
int t,n,m,k;
string a,b;int dp[2][100005];
int main(){
	freopen("D.in","r",stdin);
	freopen("D.out","w",stdout);
	scanf("%d",&t);
	while(t--){	
      memset(dp,0x3f,sizeof dp);
		scanf("%d",&k);
		cin>>a>>b;
		n=a.size();
		m=b.size();
		dp[0][0]=0;
		int last=0,now=1;
		for(int i=1;i<=m;i++){dp[last][i]=i;}
		for(int i=1;i<=n;i++){
			for(int j=max(i-k,1);j<=min(m,i+k);j++){
				if(a[i-1]==b[j-1]){
					dp[now][j]=dp[last][j-1];
				}
				else{
					dp[now][j]=min({dp[last][j],dp[last][j-1],dp[now][j-1]})+1;
				}
			}
			last^=1;
			now^=1;
		} 
		if(dp[last][m]<=k){
			printf("Yes\n");
		}
		else{
			printf("No\n");
		}
	}
	return 0;
}

错误原因：初始化不应该是0，应为取 $min$ 所以应是正无穷
本题其实从编辑距离过来的，最朴素的思路就是看看最后的 $dp_{i,j}$ 是否大于 $k$
但是这样的话时间复杂度是 $O(n^2)$ ，会超时，我们想想，哪些值一定大于 $k$ ，没错就是 $|i-j|>k$ 的时候，所以我们可以求出来 $j$ 的范围，即 $i-k \le j \le i+k$ ，为防止越界我们让 $i-k$ 与 $1$ 取 $max$ ，让 $i+k$ 与 $m$ （字符串 $b$ 的长度）取 $min$ ，这样时间复杂度就变成了 $O(n \times 2 \times k)$
还有一个严峻的问题，就是空间，学过动态规划的同学就会很简单的想到滚动数组（之前在笔记里有提到过），还有更聪明的同学（比如我）会想到直接把第一维优化掉，然后从大到小遍历，但经过亲爱的助教检查，会发现遗漏了 $f_{i,j-1}$ ，所以只能老实的写滚动数组了QWQ

8.7休息日！

上午呢我是去的解剖青蛙（这辈子再也不去了/ex），把青蛙的头剪下来，保留脊髓，做搔扒实验，在开膛剖肚……，很有罪恶感
下午呢就是去学的魔术，回来之后老师采访我了一下，说我要多练动态规划（~~那玩意谁想练啊~~）
一天内剩下的时间就是在和cys打拳皇，或者和ghk打扑克
晚上的时候去听了一个科学讲座，老师用钢管发出声音（不是钢管落地），所有人没一个成了（xswl）
美好的一天就结束了QAQ

8.8二分&倍增

小贝的守卫

CPP

#include<bits/stdc++.h>
#define int long long
using namespace std;
int n,a[200005],q;
int f1[200005];
int f2[200005];
signed main(){
	freopen("Guard.in","r",stdin);
    freopen("Guard.out","w",stdout);
	scanf("%lld%lld",&n,&q);
	for(int i=1;i<=n;i++){
		scanf("%lld",&a[i]);
		f1[i]=f1[i-1]+a[i];
	}
	for(int i=n;i>=1;i--){
		f2[i]=f2[i+1]+a[i];
	}
	sort(f2+1,f2+n+1);
	while(q--){
		int x;
		scanf("%lld",&x);
		int l=upper_bound(f1+1,f1+n+1,x)-f1;
		int r=upper_bound(f2+1,f2+n+1,x)-f2;
		r=n-r+1;
		if(l>r){
			printf("Zombies ate your brain!\n");
		}
		else{
			printf("%lld\n",n-l-(n-r-1));
		}
	}
	return 0;
}

#define int long long好习惯(bushi)
这道题其实只需要一个前缀和、一个后缀和，每秒消耗一点体力,所以在前缀和和后缀合里找第一个比 $t$ 大的下标，要注意的是后缀和是一个降序的，所以需要翻过来，得到的真实下标是 $n-r+1$ ，然后如果 $l > r$ 那么就是僵尸吃掉了你的脑子！否则输出 $n-l-(n-r+1)$ ,这里就是错误点， $r$ 表示有 $n-r-1$ 个人！

秦腾与教学评估

CPP

#include<bits/stdc++.h>
#define int long long
using namespace std;
int t;
int n;
int s[200005],e[200005],d[200005];
int func(int mid){
	int cnt=0;
	for(int i=1;i<=n;i++){
		if(s[i]<=mid){
			cnt+=(min(mid,e[i])-s[i])/d[i]+1;
		}
	}
	return cnt;
}
signed main(){
	scanf("%lld",&t);
	while(t--){
		scanf("%lld",&n);
		for(int i=1;i<=n;i++){
			scanf("%lld%lld%lld",&s[i],&e[i],&d[i]);
		}
		int l=0,r=0x7ffffffff,ans;
		while(l<=r){
			int mid=l+(r-l)/2;
			if(func(mid)%2==0){
				l=mid+1;
			}
			else{
				r=mid-1;
				ans=mid;
			}
		}
		if(func(ans)%2) printf("%lld %lld\n",ans,(func(ans)-func(ans-1)));
		else printf("Poor QIN Teng:(\n");
	}
	return 0;
}

这道题最暴力的想法就是模拟加1的过程
偶数+偶数=偶数，奇数+奇数=偶数，but奇数+偶数=偶数（虽然众所周知，但在这道题里挺关键的）
由最暴力的想法可以想到，我们在判断奇数的时候可以用到上边的思想，就是求一个前缀和，当有一个奇数时，剩下的都是奇数，基于这个思想，我们能写出二分
check函数就是计算前面的前缀和，就是便利每个 $s e d$ 求出前面点的贡献
最后输出判断这个数是否是奇数，即 $func(ans)-func(ans-1)$ 是否是奇数即可

Bessie的巧克力谜题

CPP

#include<bits/stdc++.h>
#define int long long
using namespace std;
int n,d,a[50005],sum,ans;
vector <int> s(500005);
bool _(int m){
	vector <int> v(n+1);
	int now=0,l=1;
	for(int i=1;i<=d;i++){
		
		while(now<m&&l<=n){
			now+=a[l];
			v[l]=i;
			l++;	
			
		}
		if(now<m) return 0;
		now/=2;
	}
	s=v;
	return 1;
}
signed main(){
	scanf("%lld%lld",&n,&d);
	for(int i=1;i<=n;i++){
		scanf("%lld",&a[i]);
		sum+=a[i];
	}
	int l=0,r=sum+1;
	while(l<=r){
		int m=l+(r-l)/2;
		if(_(m)){
			l=m+1;
			ans=m;
		}
		else r=m-1;
	}
	printf("%lld\n",ans);
	for(int i=1;i<=n;i++){
		if(s[i]) printf("%lld\n",s[i]);
		else printf("%lld\n",d);
	}
	return 0;
}

$r$ 要等于 $a_i$ 之和加1！
这道题其实很好想的，就是二分答案，只要当前幸福值小于 $mid$ 就吃巧克力，判断能不能吃到最后一天即可
注意，如果有的巧克力不需要吃，那么就在最后一天吃

宝物筛选

CPP

#include<bits/stdc++.h>
using namespace std;
int n,W,cnt;
int v[100005],w[100005],m[100005],f[100005];
int a[100005],b[1000005];
int main(){
	scanf("%d%d",&n,&W);
	for(int i=1;i<=n;i++){
		scanf("%d%d%d",&v[i],&w[i],&m[i]);
		int k=1;
		while(m[i]>=k){
			int kv=k*v[i];
			int kw=k*w[i];
			a[++cnt]=kv;
			b[cnt]=kw;
			m[i]-=k;
			k*=2;
		}
		if(m[i]>0){
			int kv=m[i]*v[i];
			int kw=m[i]*w[i];
			a[++cnt]=kv;
			b[cnt]=kw;
		}
	}
	for(int i=1;i<=cnt;i++){
		for(int j=W;j>=b[i];j--){
			f[j]=max(f[j],f[j-b[i]]+a[i]);
		}
	}
	printf("%d",f[W]);
	return 0;
}

~~这道题是110分~~
123集训的时候，闫老师给讲的，鸣谢
这道题其实就是把物品按照二进制打包，转化成01背包

Cyclic Array

CPP

#include<bits/stdc++.h>
#define int long long
using namespace std;
int n,k,ans=0x7ffffffffff;
int a[400005];
int f[400005][25];
signed main(){
	scanf("%lld%lld",&n,&k);
	for(int i=1;i<=n;i++){
		scanf("%lld",&a[i]);
		a[i+n]=a[i];
	}
	int r=1;
	int sum=0;
	for(int l=1;l<=2*n;l++){
		while(r<=n*2&&sum+a[r]<=k){//这里的判断需要注意一下，双指针不太熟练，有些边界需要注意
			sum+=a[r];
			r++;
		}
		f[l][0]=r;//这里不是r+1是因为我在while结束的时候已经加了1
		sum-=a[l];
	}
	for(int j=1;j<=20;j++){//这里要通过小状态推大状态
		for(int i=1;i<=n*2;i++){//模拟环
			if(f[i][j-1]>=2*n+1) f[i][j]=2*n+1;//如果f[i][j-1]已经超了边界，那么f[i][j]一定也超了边界
			else f[i][j]=f[f[i][j-1]][j-1];//状态转移
		}
	}
	for(int i=1;i<=n;i++){//暴力枚举起点
		int now=i,step=0;//now是当前的点，i是起点；cnt是跳的步数
		for(int j=20;j>=0;j--){//亲爱的助教说从大到小会尽快一点
			if(f[now][j]>=i+n){//判断是否能走完一次 
				ans=min(ans,(1<<j)+step);//走了2^j+step步 
			}
			else{//不能的话要继续走ououou~ 
				step+=1<<j;
				now=f[now][j];
			}
		}
	}
	printf("%lld",ans);//千万不能忘了输出 
	return 0;
}

这道题最暴力的就是枚举出发点，时间复杂度 $O(n^2)$
st表是非常好的东西，基于倍增的思想
$f_{i,j}$ 表示的是从第 $i$ 个点开始，分成 $2^j$ 个区间的下一个，那么我们用双指针写出 $f_{i,0}$ 的值，然后先枚举 $j$ 再枚举起点，就可以推出状态转移公式， $f_{i,j}=f_{f_{i,j-1},j-1}$ ，但是如果 $f_{i,j-1}$ 已经超出范围了我们就要也把 $f_{i,j}$ 标记成超范围
答案的话就要枚举起点，枚举 $j$ （从大到小会快），这里需要一个 $now$ 来维护当前走到了哪个点， $step$ 维护步数，判断如果 $f_{now,j}>=i+n$ ，即走完了一圈就要记录答案( $2^j+step$ )；否则就要把 $now$ 更新成 $f_{now,j}$ ， $step$ 加上 $2^j$ 。最后输出即可

8.9模考

田忌赛马

CPP

#include<bits/stdc++.h>
using namespace std;
int a[5];
int b[5];
int win,lose;
int main(){
	freopen("A.in","r",stdin);
	freopen("A.out","w",stdout);
	scanf("%d%d%d%d%d%d",&a[1],&a[2],&a[3],&b[1],&b[2],&b[3]);
	sort(a+1,a+4);
	sort(b+1,b+4);
	int l=1,r=3;
	int x=1,y=3;
	while(l<=r&&x<=y){
		if(b[l]>a[x]){
			l++;
			x++;
			win++;
		}
		else if(b[r]>a[y]){
			r--;
			y--;
			win++;
		}
		else{
			l++;
			y--;
			lose++;
		}
	} 
	if(win>lose){
		printf("Yes");
	}
	else{
		printf("No");
	}
	return 0;
}

非常标准的田忌赛马，没啥好说的

地精的金币

CPP

#include<bits/stdc++.h>
#define int long long
using namespace std;
map <char,int> m;
int n;
string s;
signed main(){
	scanf("%lld",&n);
	cin>>s;
	for(auto i:s){
		m[i]++;
	}
	if(m['-']<2||m['_']<1){
		printf("0");
		return 0;
	}
	int left=m['-']/2;
	int right=m['-']-left;
	printf("%lld",left*m['_']*right);
	return 0;
}

考试的时候就推出来了，明显是把-分两半即可，数学问题
~~十年oi一场空，XXXXX~~

数矩形

CPP

#include<bits/stdc++.h>
#define int long long
using namespace std;
int n,m,k,ans,a[100006],f[100006];
signed main(){
	scanf("%lld%lld%lld",&n,&m,&k);
	for(int i=1;i<=n;i++){
		scanf("%lld",&a[i]);
		f[i]=f[i-1]+a[i];
	}
	for(int i=1;i<=n;i++){
		int l=lower_bound(a+i+1,a+n+1,1+k+a[i])-a;
		int r=upper_bound(a+i+1,a+n+1,m+k+a[i])-a;
		r--;
		if(l!=n+1&&r!=n+1)ans+=(r-l+1)*(m+a[i]+k+1)-f[r]+f[l-1];
		l=lower_bound(a+i+1,a+n+1,1+a[i]-k)-a;
		r=upper_bound(a+i+1,a+n+1,m-k+a[i])-a;
		r--;
		if(l!=n+1&&r!=n+1)ans+=(r-l+1)*(m+a[i]-k+1)-f[r]+f[l-1];
	}
	printf("%lld",ans);
	return 0;
}

~~十年oiXXX，XXXXXXX~~
先说矩形横的时候：不难，其实从暴力就是枚举 $a_i$ 和 $a_j$ 但是会超时，所以只枚举 $a_i$ ，然后就可以写出一个不等式（ $a_j-a_i=矩形的长$ ）： $1 \le a_j-a_i-k \le m$ 通过移项可得 $1+a_i+k \le a_j \le m+a_i+k$ ，根据这个等式就可以得到一个 $a_j$ 的取值范围 $l - r$ ，lower_bound()和upper_bound()即可，注意，这里开始需要从 $i+1$ 开始会避免很多不必要的麻烦，最后我们求一下答案：单独一个 $a_j$ 时矩形个数时（合法情况下） $answer=m-(a_j-a_i-k)$ 即 $m-a_j+a_i+k$ ，然后再求 $j+1$ 、 $j+2$ 会发现每次只有 $a_j$ 这个值不一样，所以把一样的值拿出来( $m+a_i+k$ ) ，剩下的求一个前缀和 $f_i$ ，得出 $answer=(r-l+1) \times (m+a_i-k+1)-f_r+f_{l-1}$
当矩形竖着的时候就可以推出 $answer=(r-l+1) \times (m+a_i-k+1)-f_r+f_{l-1}$

小信打扑克

CPP

#include<bits/stdc++.h>
using namespace std;
int n,ans=0x7fffffff;
vector <int> cnt={1,2,3,4};
vector<char> c;
vector <int> v;
vector <int> V;
int func(){
	vector <int> a;
	for(int i=0;i<v.size();i++){
		auto q=lower_bound(a.begin(),a.end(),v[i]);
		if(q!=a.end()) *q=v[i];
		else a.push_back(v[i]);
	}
	return a.size();
}
int main(){
	scanf("%d",&n);
	for(int i=1;i<=n;i++){
		char a;
		int b;
		cin>>a>>b;
		V.push_back(b);
		c.push_back(a);
	}
	do{
		v=V;
		map <char,int> m;
		for(int i=0;i<4;i++){
			if(cnt[i]==1){
				m['C']=i;
			}
			else if(cnt[i]==2){
				m['A']=i;
			}
			else if(cnt[i]==3){
				m['M']=i;
			}
			else{
				m['P']=i;
			}
		}
		m['X']=4;
		for(int i=0;i<n;i++){
			v[i]=m[c[i]]*n+v[i];
		}
		ans=min(ans,n-func());
	}while(next_permutation(cnt.begin(),cnt.end()));
	printf("%d",ans);
	return 0;
}

next_permutatin可以枚举全排列
这道题其实就是导弹拦截，老师一讲就看出来了aaa……就是找最长上升子序列
这道题需要确定 $C、A、M、P$ 之间的顺序（ $X$ 肯定在最后），根据这个顺序给他们附一个新的权重，根据这个权重求最长上升子序列（要 $O(n \log n)$ 的算法），比如说 $C1<A10<M3<P1$ ，类似的，所以（举例）给所有 $C$ 加上0个 $n$ ，所有 $A$ 加上1个 $n$ ……
这里要注意的是数组如果修改需要还原，血的教训

8.10搜索

Stone XOR

CPP

#include<bits/stdc++.h>
#define int long long
using namespace std;
int n,answer,b[20];
int a[20],m=0; 
unordered_map <int,int> mp;//记录答案
void dfs(int idx){//记录当前下标 
	if(idx>n){
		int ans=0;
		for(int i=1;i<=m;i++){
			ans^=a[i];
		}
		mp[ans]=1;
		return ;
	}
	for(int i=1;i<=m;i++){
		a[i]+=b[idx];
		dfs(idx+1);
		a[i]-=b[idx];
	}
	m++;
	a[m]+=b[idx];
	dfs(idx+1);
	a[m]-=b[idx];
	m--;
	return ;
} 
signed main(){
	scanf("%lld",&n);
	for(int i=1;i<=n;i++){
		scanf("%lld",&b[i]);
	}
	dfs(1);
	printf("%lld",mp.size());
	return 0;
}

这道题就是模拟一个一个放石头的全部情况，要么把当前石头放进任意一堆，或者给他单开一堆，最后统计答案
信友队上的数据太水了，还得看AT上的，要用unordered_map否则会超时

Find The Multiple

CPP

#include<bits/stdc++.h>
#define int long long
using namespace std;
map <int,bool> m;
int n;
void bfs(){
	queue <pair<string,int> > q;
	q.push({"1",1%n});
	while(!q.empty()){
		auto u=q.front();
		q.pop();
		if(u.second==0){
			cout<<u.first<<"\n";
			return ;
		}
		if(!m[(u.second*10+1)%n]){
			m[(u.second*10+1)%n]=1;
			q.push({u.first+"1",(u.second*10+1)%n});
		}
		if(!m[u.second*10%n]){
			m[u.second*10%n]=1;
			q.push({u.first+"0",u.second*10%n});
		}
	}
	return ;
}
signed main(){
	while(1){
		m.clear();
		scanf("%lld",&n);
		if(n==1){
			printf("1\n");
			continue;	
		} 
		
		if(n)bfs();
		else return 0;
	}
	return 0;
}

这道题要知道的是 $(a \times 10 + b) \mod c = (a \times 10 \mod c + b) \mod c$
然后我们枚举每位放0或1即可

小信的护城河

CPP

#include<bits/stdc++.h>
using namespace std;
int a[10][10],ans;
int X[]={0,1,-1,0,0};
int Y[]={0,0,0,-1,1};
int f[10][10],ff[10][10];
void solve(int x,int y,int num){//处理连通块 
	queue <pair<int,int> > q;
	q.push({x,y});
    ff[x][y]=-1;
	while(!q.empty()){
		auto u=q.front();
		q.pop();
		for(int i=1;i<=4;i++){
			int idx=u.first+X[i];
			int idy=u.second+Y[i];
			if(idx<0||idx>5||idy<0||idy>5||ff[idx][idy]!=num) continue;
			q.push({idx,idy});
			ff[idx][idy]=-1;
		}
	} 
}
void dfs(int x,int y){//枚举可能情况 
	if(y==5){
		x++;
		y=1;
	}
	if(x==5){//结束了判断合法 
		for(int i=0;i<=5;i++){//复制一份数组 
			for(int j=0;j<=5;j++){
				ff[i][j]=f[i][j];
			}
		}
		for(int i=1;i<=4;i++){//处理联通1 
			bool flflf=0;
			for(int j=1;j<=4;j++){
				if(f[i][j]==1){
					solve(i,j,1); 
					flflf=1;
					break;
				}
				
			}
			if(flflf) break;
		}
		
		for(int i=1;i<=4;i++){
			for(int j=1;j<=4;j++){
				if(ff[i][j]==1){
					return ;
				} 
			}
		}
		solve(0,0,0);//处理联通0
		for(int i=1;i<=4;i++){
			for(int j=1;j<=4;j++){
				if(ff[i][j]==0){
					return ;
				} 
			}
		}
		ans++;
		return ;
	}
	if(a[x][y]==1){//当前点是村庄 
		f[x][y]=1;
		dfs(x,y+1);
	}
	else{//不是村庄 
		f[x][y]=1;
		dfs(x,y+1);
		f[x][y]=0;
		dfs(x,y+1); 
	}
} 
int main(){
	for(int i=1;i<=4;i++){
		for(int j=1;j<=4;j++){
			scanf("%d",&a[i][j]);
		}
	}
	dfs(1,1);
	printf("%d",ans);
	return 0;
}

注释挺清楚的，就是先枚举每个点围不围，然后看看是否所有的1联通，所有的0联通即可

8.11模考

赛后总结：第一题是真没想到要开long long，忘了还有乘法了，引以为戒
第二题忘了他是环了，c！没考虑环！！！！还没考虑圆周长不能整除的情况
$All \ in \ all$ ，本场考试心浮气躁，平常应该注意的都没注意，属实不应

小信爱音游

CPP

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=1005; 
int t;
int n;
struct node{
	int t,x,y; 
}a[N];
signed main(){
	scanf("%lld",&t);
	while(t--){
		double ans=-1;
		scanf("%lld",&n);
		for(int i=1;i<=n;i++){
			scanf("%lld%lld%lld",&a[i].t,&a[i].x,&a[i].y);
		}
		for(int i=1;i<n;i++){
			ans=max(ans,sqrt((a[i].x-a[i+1].x)*(a[i].x-a[i+1].x)+(a[i].y-a[i+1].y)*(a[i].y-a[i+1].y))/(a[i+1].t-a[i].t));
		}
		printf("%.10lf\n",ans);
	}
	return 0;
}

十年oi一场空，不开long long见祖宗
没啥好说的，模拟即可

寻找等边三角形

CPP

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+5;//数组大小 
int n,len,ans;
int a[N];
int f[N];//前缀和 
int main(){//枚举两点之间长度+二分查找 X 
	scanf("%d",&n);
	for(int i=1;i<=n;i++){
		scanf("%d",&a[i]);
	} 
	for(int i=1;i<=n;i++){
		f[i]=f[i-1]+a[i-1];
		f[i+n]=f[i];
	}
	len=(f[n]+a[n])/3;//确定边长 
	if(len*3!=f[n]+a[n]){
		printf("0");
		return 0;
	}
	for(int i=1;i<=n;i++){
		int j=lower_bound(f+i,f+2*n+1,f[i]+len)-f;
		if(j==n+1) continue;
		int k=lower_bound(f+i,f+2*n+1,f[j]+len)-f;
		if(k==n+1) continue;
		
		if(f[j]-f[i]==len&&f[k]-f[j]==len) ans++;
	} 
	printf("%d",ans); 
	return 0;
}
/*
如果三点能围城等边三角，那么他们之间在圆上的距离应相等 
双指针？ X
点和长度只能枚举一个，而我们那至少要确定一个点,枚举，根据圆的周长我们能求出三角形边长 
*/

小信学习欧几里得算法

CPP

#include<bits/stdc++.h>
using namespace std;
const int N=1e7+5;
int prive[N];
int f[N];
int t,n,ans;
int main(){
	freopen("B.in","r",stdin);
	freopen("B.out","w",stdout);
	for(int i=2;i<=N;i++){//素数筛(埃式筛 
		if(prive[i]==0){
			prive[i]=1;
			for(int j=i+i;j<=N;j+=i){
				prive[j]++;
			}
		}
	}
	for(int i=1;i<=N;i++){
		f[i]=f[i-1]+prive[i];
	} 
	scanf("%d",&t);
	while(t--){
		int n;
		scanf("%d",&n);
		printf("%d\n",f[n]);
	}
	return 0;
}
/*
O(t * sqrt(n) ) 过不了
第一感觉 dp or 数学规律 
想不出来aaaaaaa…
只能写30%了QWQ 
赛后： 
*/

$gcd 和 lcm 之间有个性质，就是 \\ a= p_1^{a_1} \times p_2^{a_2} \times p_3^{a_3}… \\b= p_1^{b_1} \times p_2^{b_2} \times p_3^{b_3}… \\ 那么 \\gcd(a,b)=p_1^{min(a_1,b_1)} \times p_2^{min(a_2,b_2)} \times p_3^{min(a_3,b_3)}… \\ lcm(a,b)=p_1^{max(a_1,b_1)} \times p_2^{max(a_2,b_2)} \times p_3^{max(a_3,b_3)}… \\ 所以我们可以得出 \\ lcm(a,b) \div gcd(a,b)=p_1^{max(a_1,b_1)-min(a_1,b_1)} \times p_2^{max(a_2,b_2)-min(a_1,b_1)} \times p_3^{max(a_3,b_3)-min(a_1,b_1)} \\ 又因为\frac{lcm(a,b)}{ gcd(a,b)}需要是质数，所以就可以得出 \\ \\ p_1^{max(a_1,b_1)-min(a_1,b_1)} \times p_2^{max(a_2,b_2)-min(a_1,b_1)} \times p_3^{max(a_3,b_3)-min(a_1,b_1)} \\ 仅有一个质因数的质数是1，其余都是0，所以可以得出 \\ a \times p = b$
这道题用埃式筛是因为他一个数能被多个数标记，所以就可以用这个性质来判断当前这个数有多少质因数
经上两个思想我们可以得出答案是小于等于n的所有数的质因数数量和，但因为 $t \le 10^6$ ，所以要预处理出所有答案

元宵灯会

CPP

#include<bits/stdc++.h>
#define int long long
using namespace std;
string s;
int n,total;
struct node{
	int left_son=-1;//左儿子 
	int right_son=-1;//右儿子 
	int father;//父节点 
	int black;//是否是灯谜 
}tree[100005];
void build(){//建树 
	int now=1;
	int it=1;
	for(int i=1;i<s.size();i++){
		if(s[i]=='('){
			if(tree[it].left_son==-1){//放左儿子 
				now++;
				tree[it].left_son=now;
				tree[now].father=it;
				it=now;
			}
			else{//放右儿子 
				now++;
				tree[it].right_son=now;
				tree[now].father=it;
				it=now;
			}
		}
		else if(s[i]==')'){//回溯到他的父节点 
			it=tree[it].father;
		}
		else{//标记有灯谜 
			total++;
			tree[it].black=1;
		}
	}
} 
bool is_leave(int u){//判断叶子结点 
	if(tree[u].left_son==-1&&tree[u].right_son==-1) return 1;
	return 0;
}
int cal(int u,int tot){//计算步数 
	if(is_leave(u)&&tot>1) return 0x7fffffff;
	if(is_leave(u)){
		if(tot==1){
			if(tree[u].black==1) return 0;
			else return 1;
		}
		else {
			if(tree[u].black==1) return 1;
			else return 0;
		}
	} 
	int less=tot/2;
	int more=tot-less;
	return min(cal(tree[u].left_son,less)+cal(tree[u].right_son,more),cal(tree[u].left_son,more)+cal(tree[u].right_son,less));
}
signed main(){
	cin>>s;
	build();
	if(cal(1,total)>=0x7fffffff) cout<<"impossible";
	else cout<<cal(1,total)/2;
	return 0;
}

纯搜索，注释挺清楚的
这道题一共有两个点
1.建树，需要一个指针指向当前点和一个点的数量，接下来遍历字符串，如果是(就新加一个点优先放左子树；如果是)就回溯到父节点；若是B就把这个点标记成有灯谜
2.计算答案，在遍历时记录下B的总个数，然后平分（注意奇数），最后到叶子结点，如果需要放的B大于1就不行，返回极大值，如果可以就通过找规律发现直接返回 $tot \oplus black$ ，最后判断一下答案即可

8.12图论

小埋学习图之环问题

CPP

#include<bits/stdc++.h>
using namespace std;
int n,m,ans=0x7fffffff;
vector <int> v[1005];
int f[1005];
void bfs(int root){
    for(int i=1;i<=n;i++){
        f[i]=0x7ffffff; 
    }
    f[root]=0;
    queue <pair<int,int>> q;
    q.push({-1, root}); 
    
    while(!q.empty()){
        auto u=q.front();
        q.pop();
        int parent = u.first;
        int current = u.second;
        
        for(int it:v[current]){
            if(it == parent) continue;
            
            if(f[it]==0x7ffffff){
                f[it] = f[current] + 1;
                q.push({current, it});
            } else {
                ans = min(ans, f[current] + f[it] + 1);
            }
        }
    }
}
int main(){
    scanf("%d%d",&n,&m);
    for(int i=1;i<=m;i++){
        int x,y;
        scanf("%d%d",&x,&y);
        v[x].push_back(y);
        v[y].push_back(x);
    }
    for(int i=1;i<=n;i++){
        bfs(i);
    }
    printf("%d",ans==0x7fffffff?-1:ans);
    return 0;
}

就是枚举环的起点，然后根据广搜最短路就可以得到以这个点为起点的最短环，注意要记录这个点从哪来的，把父节点continue掉，最后统计答案

封锁阳光大学

CPP

#include<bits/stdc++.h>
#define int long long 
using namespace std;
const int N=1e4+5;
int n,m;
int color[N];//每个点的颜色 
vector <int> g[N];//邻接表 
int ans;//记录答案 
bool flag;
void bfs(int root){
	queue <pair<int,int> > q;//点和颜色
	int num[2]={0};//统计个数 
	num[1]++;//一开始的root是1 
	q.push({root,1});
	color[root]=1;
	while(!q.empty()){
		auto u=q.front();
		q.pop();
		if(color[u.first]==-1){//
			color[u.first]=u.second;
			num[u.second]++;
		}
		else{
			if(color[u.first]!=u.second){
				flag=1;
				break;
			}
		}
		for(auto it:g[u.first]){
			if(color[u.first]==color[it]){
				
				flag=1;
				break;
			}
			if(color[it]==-1){
				color[it]=u.second^1;
				num[u.second^1]++;
				q.push({it,u.second^1});
			}
		}
	} 
	ans+=min(num[0],num[1]);
	return ;
} 
signed main(){
	memset(color,-1,sizeof(color));//初始化 
	scanf("%lld%lld",&n,&m);
	
	for(int i=1;i<=m;i++){
		int u,v;
		scanf("%lld%lld",&u,&v);
		g[u].push_back(v);
		g[v].push_back(u);
	}
	for(int i=1;i<=n;i++){
		if(color[i]==-1){//遍历每个连通图 
			bfs(i);
			if(flag){//无法封锁所有道路
				printf("Impossible");
				return 0;
			}
		}
	}
	printf("%lld",ans);
	return 0;
}

其实想地图涂色，相邻的两点不能涂成同一颜色，否则就是答案不合法，注意最后取答案时要在两个颜色数量之间取 $min$ ，还有这个题没有保证时连通图，所以要分别求答案取和

Hidden Weights

CPP

#include<bits/stdc++.h>
#define int long long 
using namespace std;
const int N=2*1e5+5;
int n,m;
vector <pair<int,int> > g[N]; 
int ans[N];
bool vis[N];
void bfs(int root){
	queue<int>q;
	q.push(root);
	vis[root]=1;
	while(!q.empty()){
		int u=q.front();
		for(auto i:g[u])
			if(!vis[i.first]){
				vis[i.first]=1;
				ans[i.first]=ans[u]+i.second;
				q.push(i.first);
			}
		q.pop();
	}
	return ;
} 
signed main(){
	scanf("%lld%lld",&n,&m);
	for(int i=1;i<=m;i++){
		int u,v,w;
		scanf("%lld%lld%lld",&u,&v,&w);
		g[u].push_back({v,w});
		g[v].push_back({u,-w});
	}
	for(int i=1;i<=n;i++){
		if(vis[i]==0){
			bfs(i);
		}
	}
	for(int i=1;i<=n;i++){
		printf("%lld ",ans[i]);
	}
	return 0;
}

跟上一道题差不多，但唯一一个思维点就是放的时候要当无向图存，边权取相反数，最后看看放哪个数即可

图的m着色问题

CPP

#include<bits/stdc++.h>
using namespace std;
vector <int> g[105];
int n,k,m,ans;
int color[105];
void dfs(int u){
	map <int,int> mp; 
	if(u>n){
		ans++;
		return ;
	}
	for(auto it:g[u]){
		mp[color[it]]++;
	}
	for(int i=1;i<=m;i++){
		if(mp[i]==0){
			color[u]=i;
			dfs(u+1);
			color[u]=0;
		}
	}
}
int main(){
	scanf("%d%d%d",&n,&k,&m);
	for(int i=1;i<=k;i++){
		int u,v;
		scanf("%d%d",&u,&v);
		g[u].push_back(v);
		g[v].push_back(u);
	}
	dfs(1);
	printf("%d",ans);
	return 0;
}

这道题一年前就A了，鸣谢al111111
这道题就是枚举每个点的颜色，然后根据可行性剪枝，最后统计答案

NOIP2014-S-DAY2-2-寻找道路

CPP

#include<bits/stdc++.h>
#define pb push_back
using namespace std;
int n,m,s,t;
int may[10005],maybe[10005];//标记是否能用 
vector <int> fw[10005];//正向 
vector <int> bw[10005];//反向建边 
void back(int root){
	bool vis[10005]={0};
	queue <int> q;
	q.push(root);
	vis[root]=1;
	may[root]=1;
	while(!q.empty()){
		auto u=q.front();
		q.pop();
		for(auto it:bw[u]){
			if(!vis[it]){
				vis[it]=1;
				may[it]=1;
				q.push({it});	
			}
		}
	}
	return ;
}
struct node{
	int u,step;
};
int bfs(int root){
	queue <node> q;
	q.push({root,0});
	int vis[10005]={0};
	vis[root]=1;
	while(!q.empty()){
		auto u=q.front();
		q.pop();
		if(u.u==t){
			return u.step;
		}
		for(auto it:fw[u.u]){
			if(!vis[it]&&maybe[u.u]){
				vis[it]=1;
				q.push({it,u.step+1});
			}
		}
	}
	return -1;
}
int main(){
	scanf("%d%d",&n,&m);
	for(int i=1;i<=m;i++){
		int x,y;
		scanf("%d%d",&x,&y);
		fw[x].pb(y);
		bw[y].pb(x);//反向建边 
	}
	scanf("%d%d",&s,&t);
	back(t); 
	for(int i=1;i<=n;i++){//判断能不能用这个点
		int fl=1;
		for(auto it:fw[i]){//枚举
			if(may[it]==0) fl=0;
		} 
		maybe[i]=fl;
	}
	if(maybe[s]==0){
		printf("-1");
		return 0;
	}
	printf("%d",bfs(s));
	return 0;
}

这道题分两步
1.把能到达终点的点标记一下，然后根据题目的第一个特性把能用的点根据是否能到达终点标记一下
2.用广搜在可用的点里找最短路

NOIP2002-J-3-产生数

CPP

#include<bits/sdc++.h>
using namespace std;
__int128 ans=1;
int n;
void out(__int128 x)
{
    if(x<0)putchar('-'),x=-x;
    if(x<10)putchar(x+'0');
    else out(x/10),putchar(x%10+'0');
}
string s;
vector <int> v[10];
int bfs(int root){
	int num=1;
	queue <int> q;
	int vis[10]={0};
	q.push(root);
	vis[root]=1; 
	while(!q.empty()){
		auto u=q.front();
		q.pop();
		for(auto it:v[u]){
			if(vis[it]==0){
				q.push(it);
				vis[it]=1;
				num++;
			}
		}
	}
	return num;
}
int main(){
	cin>>s>>n;
	for(int i=1;i<=n;i++){
		int x,y;
		scanf("%d%d",&x,&y);
		v[x].push_back(y);
	}
	for(auto it:s){
		ans*=bfs(it-'0');
	}
	out(ans);
	return 0;
}

~~也是浅浅取抄了一下快写的题解好吧~~
这道题其实不难，经过小学数学就可以得出总答案时每个位置上可选的数的乘积就是答案，根据搜索可以得出每个位置可以放的数的数量，最后乘起来，注意这道题每个位置有10个可能，共30位，那么是 $10^30$ ,所以要请出唯一真神__int128！！！！

8.13模考

石头布

CPP

#include<bits/stdc++.h>
using namespace std;
string s;
int pts,x,y;
int main(){
	cin>>s;
	for(auto it:s){
		if(x>y){
			y++;
			if(it=='g')pts++;
		} 
		else{
			x++;
			if(it=='p') pts--;
		}
	}
	printf("%d",pts);
	return 0;
}

有点贪心的影子，我举了几个例子发现只要能出布就出布，只需要判断得分就行

忙碌的老师

CPP

#include<bits/stdc++.h>
using namespace std;
int n,ans,now;
map <int,int> m;
int main(){
	scanf("%d",&n);
	for(int i=1;i<=n;i++){
		int l,r;
		scanf("%d%d",&l,&r);
		m[l]++;
		m[r+1]--;
	}
	for(auto i:m){
		now+=i.second;
		ans=max(ans,now);
	}
	printf("%d",ans);
	return 0;

}

这道题考试的时候脑子抽抽了，把sort的复杂度想成 $O( \log n)$ 了
这道题劳氏讲了之后说其实这道题本质就是给 $[l,r]$ 这个区间加一，求最大值，然后我茅厕顿开，注意范围很大，要用map

小信的su7

CPP

#include<bits/stdc++.h>
#define int long long//好习惯
#define pii pair<int,int>//不要太长 
using namespace std;
const int N=1e5+5;
int n,m,a[N],t[N],x[N],b[N];
int ed[N],last[N],ans,k=1;
queue <int> qu[N];
signed main(){
	scanf("%lld%lld",&n,&m);
	for(int i=1;i<=n;i++){
		scanf("%lld",&a[i]);
		b[i]=a[i];
	}
	for(int i=1;i<=m;i++){
		scanf("%lld%lld",&x[i],&t[i]);
		qu[t[i]].push(x[i]);
	}
	priority_queue<pii,vector<pii>,greater<pii> > q;
	for(int i=1;i<=n;i++){
		qu[i].push(0x7fffffff);
		q.push({qu[i].front(),i});
		qu[i].pop();
	} 
	while(!q.empty()){
		auto u=q.top();
		int id=u.second;
		q.pop();
		if(k<=m&&ans+b[id]>=x[k]){
			int d=x[k]-ans;
			b[id]-=d;
			ans+=d;
			b[t[k]]=a[t[k]];
			q.push({qu[t[k]].front(),t[k]}); 
			qu[t[k]].pop();
			if(id!=t[k])
				q.push({u.first,u.second});
			k++;
		}
		else{
			
			ans+=b[id];
			b[id]=0; 
		}
	}
	printf("%lld",ans);
	return 0;
}

~~真难啊~~
一下有豆包AI生成（太难了我不会写）：代码通过优先队列（小根堆）管理不同电池的使用顺序，始终优先使用最早需要充电的电池，从而最大化行驶距离。这是一种典型的贪心策略，确保每一步都做出局部最优选择，最终达到全局最优
贪心选择的合理性：优先使用最早需要充电的电池，可以避免该电池的电量浪费（如果不使用，到达充电点后会被充满，原剩余电量作废）
充电机制：到达充电点后立即将对应电池充满，保证了资源的最大化利用
优先队列的使用：确保了每次都选择最优的电池进行消耗，时间复杂度为 O (m log n)，能够处理大规模数据

小信的符文阵列

CPP

#include<bits/stdc++.h>
#define int long long
using namespace std;
int k,n[405];
char s[405];
int mx[405][405];
int mn[405][405];
signed main(){
	memset(mx,-0x3f,sizeof(mx));
	memset(mn,0x3f,sizeof(mn));
	cin>>k;
	for(int i=1;i<=k;i++){
		cin>>n[i]>>s[i];
		n[i+k]=n[i];//初始化+模拟环 
		s[i+k]=s[i];
		mx[i][i]=n[i];
		mn[i][i]=n[i];
		mn[i+k][i+k]=n[i];
		mx[i+k][i+k]=n[i];
	}
	for(int len=2;len<=k;len++){
		for(int l=1;l+len-1<=2*k;l++){
			int r=l+len-1;
			for(int q=l;q<r;q++){
				if(s[q]=='+'||s[q]=='?'){
					mx[l][r]=max(mx[l][r],mx[l][q]+mx[q+1][r]);
					mn[l][r]=min(mn[l][r],mn[l][q]+mn[q+1][r]);
				}
				if(s[q]=='-'||s[q]=='?'){
					mx[l][r]=max(mx[l][r],mx[l][q]-mn[q+1][r]);
					mn[l][r]=min(mn[l][r],mn[l][q]-mx[q+1][r]);
				}
				if(s[q]=='*'||s[q]=='?'){
					mx[l][r]=max({mx[l][r],mx[l][q]*mx[q+1][r],mx[l][q]*mn[q+1][r],mn[l][q]*mx[q+1][r],mn[l][q]*mn[q+1][r]});
					mn[l][r]=min({mn[l][r],mx[l][q]*mx[q+1][r],mx[l][q]*mn[q+1][r],mn[l][q]*mx[q+1][r],mn[l][q]*mn[q+1][r]});
				}
			}
		}
	}
	for(int i=1;i<=k;i++){
		cout<<abs(mn[i][i+k-1])<<abs(mx[i][i+k-1]);
	}
	return 0;
}

这道题先想到搜索，但过不了，因此可以转化成区间DP
首先他是个环，所以要两倍
当运算符是加时，最大值应是左区间的最大值加右区间的最大值；最小值相反，即 $\\ mx_{l,r}=max(mx_{l,r},mx_{l,q}+mx_{q+1,r}) \\ mn_{l,r}=min(mn_{l,r},mn_{l,q}+mn_{q+1,r})$
当运算符是减号：最大值应是左区间的最大值减右区间的最小值；最小值相反，即 $\\ mx_{l,r}=max(mx_{l,r},mx_{l,q}-mn_{q+1,r}) \\ mn_{l,r}=min(mn_{l,r},mn_{l,q}+mx_{q+1,r})$
当是乘号时，四种情况都有可能，即 $\\ mx_{l,r}=max({mx_{l,r},mx_{l,q}*mx_{q+1,r},mx_{l,q}*mn_{q+1,r},mn_{l,q}*mx_{q+1,r},mn_{l,q}*mn_{q+1,r}}) \\ mn_{l,r}=min({mx_{l,r},mx_{l,q}*mx_{q+1,r},mx_{l,q}*mn_{q+1,r},mn_{l,q}*mx_{q+1,r},mn_{l,q}*mn_{q+1,r}})$

8.14休息日

感觉这个休息日没有上个休息日舒服
今天就是去了个《熊猫乐园》，《没有熊猫》，然后就是各种活动，有点没意思说实话
下午回来呢就是吃《自助餐》，然后晚上也不知道干啥（也就我写作业吧）

8.15动态规划QWQ

小信小友打怪兽

CPP

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e6+5;
int n,a[N],f[N][2];
signed main(){
	scanf("%lld",&n);
	for(int i=1;i<=n;i++){
		scanf("%lld",&a[i]);
	}
	f[1][0]=a[1];
	f[0][0]=0x7fffffff;
	f[1][1]=0x7ffffffff;
	for(int i=2;i<=n;i++){
		f[i][0]=min(f[i-1][1]+a[i],f[i-2][1]+a[i-1]+a[i]);
		f[i][1]=min(f[i-1][0],f[i-2][0]);
	}
	printf("%lld",min(f[n][0],f[n][1]));
	return 0;
}

状态含义： $f_{i,j}$ 表示第 $i$ 个怪兽由第 $j$ 个人打的最小伤害（ $j=0$ 代表小信打； $j=1$ 代表小友打）
状态转移： $j=0$ 时，小信可能就打了这一个（ $f_{i-1,1}+a_i$ ）或者连续打了两个（ $f_{i-2,1}+a_{i-1}+a_i$ ）,所以要取最小值 $f_{i,0}=min(f_{i-1,1}+a_i,f_{i-2,1}+a_{i-1}+a_i)$ ；当 $j=1$ 时就是小友打，有可能小友就打了当前这一个（ $f_{i-1,0}$ ）或者连续打了两个（ $f_{i-2,0}$ ），最后要取个最小值 $f_{i,1}=min(f_{i-1,0},f_{i-2,0})$
初始化： $f_{1,0}$ 要看 $a_1$ 的值； $f_{0,0}$ 和 $f_{1,1}$ 都是不存在的状态，要赋值成极大值

寿司选择

CPP

#include<bits/stdc++.h>
using namespace std;
int n,m;
int a[205],f[50005];
int main(){
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++){
		scanf("%d",&a[i]);
	}
	f[0]=1;
	for(int i=1;i<=n;i++){
		for(int j=50000;j>=a[i];j--){
			f[j]|=f[j-a[i]];
		}
	}
	for(int i=m;i<=50000;i++){
		if(f[i]){
			printf("%d",i);
			return 0;
		}
	}
	return 0;
}

易如反掌， $Just \ so \ so$
状态含义： $f_j$ 的含义是容量为 $j$ 的背包是否能恰好装满
状态转移：只要 $f_{i-1,j}$ 和 $f_{i-1,j-a_i}$ 中有一个是可以的那就是可以的，我这里用的是一维所以直接或上就可以
初始化：当啥都不选的时候体积就是0，所以 $f_0$ 得赋值成1

选取奶牛

CPP

#include<bits/stdc++.h>
using namespace std;
const int N=4e5;
int n;
int f[800005];
int main(){

	memset(f,-0x3f,sizeof(f));
	f[N]=0;
	scanf("%d",&n);
	for(int i=1;i<=n;i++){
		int s,d;
		scanf("%d%d",&s,&d);
		if(s>=0){
			for(int j=8e5;j>=s;j--){
				f[j]=max(f[j],f[j-s]+d);
			}
		}
		else{
			for(int j=0;j<=8e5+s;j++){
				f[j]=max(f[j],f[j-s]+d);
			}
		}
	}
	int ans=0;
	for(int i=N;i<=8e5;i++){
		if(f[i]>=0)ans=max(ans,i-N+f[i]);
	}
	printf("%d",ans);
	return 0;
}

这道题可以建一个 $f_{i,j,k}$ 表示前 $i$ 个奶牛、智商和、情商和是否存在，最后枚举 $j$ 和 $k$ 然后去最大和即可，这么一看好像没问题！于是老师HzA_anzi郑重按下了提交代码，MLE！老师微微一笑，512MB！只能开下 $1.2 \times 10^8$ 左右大小的数组，但我们开了 $3.2 \times 10^8$ 的数组
然后就会想到贪心，我们可以只枚举智商和，固定一个量让另外一个量更大，这样就能空间就够了，但是智商和有负数，我们又不能舍弃这些状态所以就有一个思想，把 $-4 \times 10^5$ ~ $4 \times 10^5$ 整体向右挪 $4 \times 10^5$ ，也就是说现在数组的 $f_0$ 其实是 $f_{-4 \times 10^5}$
在转移的时候要注意智商大于0的时候要倒着遍历；否则正着遍历，注意要判断边界
到最后便利找最大值即可

排卡

CPP

#include<bits/stdc++.h>
#define int long long 
using namespace std;
const int mod=998244353;
int qp(int a,int b) {
	if(a==0&&b==0) return 0;
    int num=1;
    while (b>0) {
        if (b&1) num=num*a%mod;
        a=a*a%mod;
        b>>=1;
    }
    return num%mod;
}
int n,t;
int f[1005][1005][2],a[1005];
signed main(){
	scanf("%lld",&t);
	while(t--){
		scanf("%lld",&n);
		memset(f,0,sizeof(f));
		for(int i=1;i<=n;i++){
			scanf("%lld",&a[i]);
		}
		for(int len=2;len<=n;len++){
			for(int l=1;l+len-1<=n;l++){
				int r=l+len-1;
 				f[l][r][0]=max(f[l+1][r][0]+qp(a[l],a[l+1]),f[l+1][r][1]+qp(a[l], a[r]));
      		    f[l][r][1]=max(f[l][r-1][0]+qp(a[r],a[l]),f[l][r-1][1]+qp(a[r], a[r-1]));
			}
		}
		printf("%lld\n",max(f[1][n][0],f[1][n][1]));
	}
	
	return 0;
}

有一位蒟蒻曾说：十年oi一场空，不开long long见祖宗
非常明显的区间DP，我们定义 $f_{l,r,0}$ 为 $[l,r]$ 序列下一个将删去最左边的数的最大得分，同理 $f_{l,r,1}$ 为 $[l,r]$ 序列下一个将删去最右边的数的最大得分。
状态转移： $\\ f_{l,r,0}=max(f_{l+1,r,0}+a_l^{a_{l+1}},f_{l+1,r,1}+a_l^{a_r}) \\ f_{l,r,1}=max(f_{l,r-1,0}+a_r^{a_l},f_{l,r-1,1}+a_r^{a_{r-1}})$
得出答案：就是 $max(f_{1,n,0},f_{1,n,1})$

花园改造

CPP

#include<bits/stdc++.h>
using namespace std;
int n,a[100005][5];
int f[100005][5][5],ans;
signed main(){
	scanf("%d",&n);
	for(int i=1;i<=n;i++){
		for(int j=0;j<3;j++){
			scanf("%d",&a[i][j]);
		}
	}
	for(int first=0;first<3;first++){//枚举第一个
		for(int second=0;second<3;second++){//枚举第二个 
			if(first==second) continue;//不合法 
			memset(f,-0x3f,sizeof(f));
			f[2][second][first]=a[1][first]+a[2][second];//初始化 
			for(int i=1;i<=n;i++){//枚举第几个点 
				for(int j=0;j<3;j++){//枚举当前点 
					for(int laster=0;laster<3;laster++){//枚举上上个点 
						for(int last=0;last<3;last++){//枚举上个点 
							if(j==last||last==laster) continue;//相邻的不能相同
							if(i==n&&j==first) continue;//相邻的不能相同
							if(last==1&&laster!=j) continue;//小树苗左右必须相同 
							if(i==n&&j==1&&last!=first) continue;//小树苗左右必须相同 
							if(i==n&&first==1&&second!=j) continue;//小树苗左右必须相同  
							//处理不合法
							f[i][j][last]=max(f[i][j][last],f[i-1][last][laster]+a[i][j]); //状态转移 
						}
					}
				}
			}
			ans=max({ans,f[n][0][1],f[n][0][2],f[n][1][2],f[n][1][0],f[n][2][0],f[n][2][1]});//记录答案 
		} 
	}
	printf("%d",ans);
	return 0;
}

~~美丽的屎山代码，与烤鸡有异曲同工之妙~~
这道题老师主打一个梦到啥写啥，先是必须的枚举 $i$ 个位置和 $j$ 种物品，但写着写着就会发现缺少一维状态，然后就增加至 $f_{i,j,k}$ 表示第 $i$ 个位置放第 $j$ 种、上一个放了第 $k$ 种物品的最大满意度，状态含义；然后继续往下写，就又会发现还不能确定上上一个的种类，所以又要枚举，接下来接着写，就会发现又又又少一个，这次是因为它是一个环，最后一个和第一个是联通的，所以我们需要枚举第一个的状态，接下来就会自然想出又双叒叕少第二个的种类，就可以再加一个for，然后再加一些处理不合法的状态和状态转移即可

小信分蛋糕2

CPP

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int mod=998244353;
int n,m,k;
int f[1005][5005],pri[1005][5005];
signed main(){
	scanf("%lld%lld%lld",&n,&m,&k);
	for(int i=1;i<=m;i++) f[1][i]=1,pri[1][i]=pri[1][i-1]+1;
	for(int i=2;i<=n;i++){
		for(int j=1;j<=m;j++){
			if(j-k>=1){
				f[i][j]+=pri[i-1][j-k];
				f[i][j]%=mod;
			}
			if(j+k<=m){
				f[i][j]+=(pri[i-1][m]-pri[i-1][j+k-1]+mod)%mod;
				f[i][j]%=mod;
			}
			if(k==0){//多算
				f[i][j]-=f[i-1][j];
			}
			pri[i][j]=pri[i][j-1]+f[i][j];
			pri[i][j]%=mod;
		}
	}
	printf("%lld",pri[n][m]%mod);
	return 0;
}

这道题也是动态规划（不是为啥我要说啊，这不是动态规划专题吗）
状态含义： $f_{i,j}$ 表示第 $i$ 个人有 $j$ 块蛋糕的方案数
推导思路，首先可以枚举上一个人有几块蛋糕，判断两人之差是否大于 $k$ ，像AI作曲，写完后就会发现是TLE！说实话写的时候就看出来了，~~老湿真坑~~，然后就可以借鉴一下AI作曲的思路，确定内层循环的范围，然后确定一个前缀和来转移状态
初始化， $f_{1,[1,m]}$ 都是一种方案，而且他的前缀和也要计算
答案，就是最后一行的前缀和，就是 $pri_{n,m}=f_{n,1}+f_{n,2}+…f_{n,m-1}+f_{n,m}$

花园改造

CPP

#include<bits/stdc++.h>
using namespace std;
int n,a[100005][5];
int f[100005][5][5],ans;
signed main(){
	scanf("%d",&n);
	for(int i=1;i<=n;i++){
		for(int j=0;j<3;j++){
			scanf("%d",&a[i][j]);
		}
	}
	for(int first=0;first<3;first++){//枚举第一个
		for(int second=0;second<3;second++){//枚举第二个 
			if(first==second) continue;//不合法 
			memset(f,-0x3f,sizeof(f));
			f[2][second][first]=a[1][first]+a[2][second];//初始化 
			for(int i=1;i<=n;i++){//枚举第几个点 
				for(int j=0;j<3;j++){//枚举当前点 
					for(int laster=0;laster<3;laster++){//枚举上上个点 
						for(int last=0;last<3;last++){//枚举上个点 
							if(j==last||last==laster) continue;//相邻的不能相同
							if(i==n&&j==first) continue;//相邻的不能相同
							if(last==1&&laster!=j) continue;//小树苗左右必须相同 
							if(i==n&&j==1&&last!=first) continue;//小树苗左右必须相同 
							if(i==n&&first==1&&second!=j) continue;//小树苗左右必须相同  
							//处理不合法
							f[i][j][last]=max(f[i][j][last],f[i-1][last][laster]+a[i][j]); //状态转移 
						}
					}
				}
			}
			ans=max({ans,f[n][0][1],f[n][0][2],f[n][1][2],f[n][1][0],f[n][2][0],f[n][2][1]});//记录答案 
		} 
	}
	printf("%d",ans);
	return 0;
}

~~美丽的屎山代码，和烤鸡有异曲同工之妙~~
这道题老师纯梦着啥写啥，首先是必须的枚举第 $i$ 个位置放第 $j$ 种树，写了一会发现不能确定上一个位置的情况，所以再加一维和for，接着写，然后发现如果上一个是小树苗，那么无法确定上一个的上一个是什么，所以再加一层for，然后因为他是环啊，最后一个位置的时候看不了第一个位置，再加一个for……，然后就可以自然而然的推出第一个位置是小树苗，第二个无法确定，又双叒叕加一个；加几个判断不合法。
状态含义： $f_{i,j,k}$ 表示第 $i$ 个位置放第 $j$ 种、前一个放的第 $k$ 种的最大满意度
状态转移，就是上一个位置加上放第 $j$ 种的满意度并取最大值即可

8.16模考

赛后总结，本次比赛心态不好，十分兴奋，考试时三心二意，没有全身心投入，属实不应，提出批评
第一题其实如果重构一遍就过了应该，而且时间完全够，考试时把时间复杂度算错了，低级失误；日后应加强调试能力，增加码力，增加做题量
第二题想得太简单了，没有认真计算，日后要增加写题前思考的步骤
第三题第四题日常骗分

小信的数学题

CPP

#include<bits/stdc++.h>
#define int long long
using namespace std;
int n,ans;
vector <char> v;
map <char,int> mp;
string s[15];
int vis[10];
map <char,int> m;
void dfs(int u){
	if(u==v.size()){//出口
		int cnt=0;
		for(int i=0;i<n-1;i++){//求加数之和
			string a=s[i];
			if(m[a[0]]==0) return ;//判断前导0
			int num=0;
			for(int j=0;j<a.size();j++){//转换成数字
				num*=10;
				num+=m[a[j]];
			}
			cnt+=num;
		}
		if(m[s[n-1][0]]==0) return ;//判断前导0
		int num=0;
		for(int j=0;j<s[n-1].size();j++){//求答案
			num*=10;
			num+=m[s[n-1][j]];
		}
		if(num==cnt){//合法
			ans++;
		}
		return ;
	}
	for(int i=0;i<=9;i++){
		if(vis[i]==0){
			vis[i]=1;
			m[v[u]]=i;
			dfs(u+1);
			vis[i]=0;
		}
	}
	return ;
}
signed main(){
	scanf("%lld",&n);
	for(int i=0;i<n;i++){
		cin>>s[i];
		for(auto it:s[i]){
			if(mp[it]==1){}
			else{//统计不同字符
				mp[it]=1;
				v.push_back(it);
			}
		}
	}
	dfs(0);
	printf("%lld",ans);
	return 0;
}

非常明显的搜索，考试就看出来了，但算错了时间复杂度，有10个位置，每个位置有10种情况，故得出结论是 $O(10^10)$ ，会超时；其实是每个位置不能相同，所以是 $O(10!)$
接下来就是深度优先搜索枚举每个字母对应什么了，注意要判前导0
还有一种枚举全排列的做法就不写了

调酒大师

CPP

#include<bits/stdc++.h>
#define int long long
using namespace std;
int n,m,t;
signed main(){
	scanf("%d",&t);
	while(t--){
		scanf("%lld%lld",&n,&m);
		printf("%lld\n",min({n,m,(n+m)/4}));
	}

	return 0;
}

好简短的数学题……枉费我模拟的苦心
调酒就是分组，每一组先放一个果汁和一个白酒，剩下两个随便放，我们设能分成 $x$ 组，然后可以得出 $x \le min(n,m)$ ，再放剩下的，是 $y=\frac{n-x+m-x}{2}$ ，要求 $x$ 最大，就要保证 $y \ge x$ ，通过移项可得 $\frac{n+m}{4} \ge x$ ，所以在 $\frac{n+m}{4}$ 和 $n,m$ 里取最小值即可

8.17数论

CPP

#include<bits/stdc++.h>
#define pb push_back
using namespace std;
int n,a[200005],ans,mx;
bool vis[1000005];
bool f[1000005];
signed main(){
	scanf("%d",&n);
	for(int i=1;i<=n;i++){
		scanf("%d",&a[i]);
		mx=max(mx,a[i]);
	}
	for(int i=1;i<=n;i++){
		if(f[a[i]]) vis[a[i]]=1;
		for(int j=a[i]*2;j<=mx+5;j+=a[i]){
			vis[j]=1;
		}
		f[a[i]]=1;
	}
	for(int i=1;i<=n;i++){
		if(vis[a[i]]==0) ans++;
	}
	printf("%d",ans);
	return 0;
}

非常明显的AT题
借鉴了埃式筛的思想，题目的意思就是在序列里不能有因数，所以我们可以把每个数的倍数筛掉，然后看有几个没被筛掉的
需要注意的是若有多个相同的数的情况，及第二个样例，需要在第二个数的时候把这个数本身筛掉( $f_i$ 的含义)
有一个点就是在 $j$ 已经被筛过了还要继续筛，毕竟埃式筛是从小到大筛的，但我筛的顺序不一定，所以不能跳出循环，比如说第三个样例，到 $a_i = 2$ 的时候筛到8的时候会直接跳出，所以18就筛不掉了

Shuffle

CPP

#include<bits/stdc++.h>
#define int long long 
#define mod 998244353
using namespace std;
int c[5005][5005],n,k,ans;
void func(){//初始化 
	for(int i=0;i<=5000;i++){
		for(int j=0;j<=i;j++){
			if(i==0||j==0||i==j) c[i][j]=1;
			else c[i][j]=c[i-1][j-1]+c[i-1][j];
			c[i][j]%=mod;
		}
	}
}
string s;
int f[5005];//前缀和 
signed main(){
	func();
	scanf("%lld%lld",&n,&k);
	cin>>s;
	for(int i=0;i<n;i++){
		if(s[i]=='1') f[i+1]=f[i]+1;
		else f[i+1]=f[i];
	} 
    if(f[n]<k){
        printf("1");
        return 0;
    } 
	for(int i=0;i<n;i++){
		for(int j=i+1;j<n;j++){
			if(f[j+1]-f[i]<=k){
				int num=f[j+1]-f[i];
				if(s[i]=='0') num--;
				if(s[j]=='0') num--;
				if(num<0)continue;
				ans+=c[j-i-1][num];
				ans%=mod;
			}
		}
	}
	printf("%lld",(ans+1)%mod);
	return 0;
}

这题发现用动态规划不好处理，于是考虑怎么处理掉本质不同这个限制，就有了一个很妙的办法，我们只关注最终的序列，并不关注在哪个区间操作了，所以可以枚举值发生变化的第一个位置 $i$ 和最后一个位置 $j$ 。发现对于不同的 $i$ , $j$ ，最终的序列是肯定不相同的，因为 $i$ , $j$ 这两个位置的值是一定改变了的
现在我们处理好了本质不同这个限制，我们还要满足对于 $k \in [i,j],s_k$ 中的 1 的个数不能超过 $k$ ，且全局中1的个数要大于等于 $k$ ，这使得这一对 $i,j$ 是合法的， $i,j$ 中的01可以随便填， $s_i,s_j$ 必须强制改变，方案数是 $C_{num_0}^{num_0+num_1}$ ， $num0,num1$ 分别表示区间里0,1的个数

[GESP202312 五级] 小杨的幸运数

CPP

#include<bits/stdc++.h>
#define int long long
#define pb push_back
using namespace std;
int a,n;
vector <int> v;
int vi[1000005];
signed main(){
	scanf("%lld%lld",&a,&n);
	for(int i=1;i<=1000001;i++){
		if(i>=a&&(long long)sqrt(i)*(long long)sqrt(i)==i){//判断完全平方数
			vi[i]=1;
			for(int j=i*2;j<=1000001;j+=i){
				vi[j]=1;
			}
		}
	}
	for(int i=1;i<=1000001;i++){
		if(vi[i]) v.pb(i);
	}
	while(n--){
		int x;
		scanf("%lld",&x);
		if(vi[x]){
			printf("lucky\n");
			continue;
		}
		printf("%lld\n",*lower_bound(v.begin(),v.end(),x));
	}
	return 0;
}

挺简单的，本蒟蒻一眼就看出来了
就是枚举大于 $a$ 的完全平方数，借助埃式筛的思想，把所有的幸运数找出来，然后二分查找
这里要注意的是判断完全平方数的地方sqrt()有些编译器会优化，且返回的值类型是double，比如锣鼓，所以要先强转一下，再判断，鸣谢亲爱的助教

Many Perfect Squares

CPP

#include<bits/stdc++.h>
#define int long long
using namespace std;
int t,mx;
signed main(){
	scanf("%lld",&t);
	while(t--){
		int n,a[55]={0};
		mx=1;
		scanf("%lld",&n);
		for(int i=1;i<=n;i++){
			scanf("%lld",&a[i]);
		}
		for(int i=1;i<=n;i++){
			for(int j=1;j<i;j++){
				for(int k=1;k<=sqrt(a[i]-a[j]);k++){
					if((a[i]-a[j])%k==0){
						int x=(a[i]-a[j])/k;
						if((k+x)%2) continue;
						int p=(k+x)/2;
						int X=p*p-a[i];
						if(X<0) continue;
						int ans=0;
						for(int q=1;q<=n;q++){
							int o=(int)(sqrt(a[q]+X));
							if(o*o==a[q]+X){
								ans++;
							}
						}
						mx=max(ans,mx);
					}
				}
			}
		}
		printf("%lld\n",mx);
	}
	return 0;
}

用了助教的神奇思路

解题思路解析

核心思路概述解决该问题的核心在于通过生成"候选x值"，并验证其平方数性，最终找到具有最大平方数性的x值。具体来说，x的平方数性取决于集合中能与x相加得到完全平方数的元素个数，因此需要精准定位可能的x值并进行验证。
1. 明确x的本质特征 x的平方数性定义为：集合中满足 $a_i + x = t^2$ （t为非负整数）的元素个数。由此可推导出：
  $x = t^2 - a_i$

这表明，有价值的x必须是某个完全平方数减去集合中的元素，无需考虑无关的x值。

2. 生成候选x值的策略

为避免遗漏可能的最优解，需从多个维度生成候选x：

（1）基于单个元素的候选x

对于集合中的每个元素(a_i)：

当(t=0)时， $x = -a_i$
若该x值非负（满足 $0 \leq x \leq 10^{18}$ ），则纳入候选集（此时 $a_i + x = 0$ ，是最小的完全平方数）

（2）基于元素对的候选x

对于集合中任意两个元素

a_i \ 和 \ a_j(i > j）

：

计算差值 $d = a_i - a_j$
若 $(a_i + x)和(a_j + x)$ 都是完全平方数（设为 $t^2$ 和 $s^2$ ），则：
$t^2 - s^2 = d \implies (t-s)(t+s) = d$
因此， $\ (t-s \ )和 \ (t+s \ )$ 是d的一对因子（设为 $\ k$ 和 $\ d \div k$ ），且两者必须同奇偶（因为 $\ t \ 和 \ s$ 为整数， $t-s + t+s = 2t$ 必为偶数）
由因子可计算 $t = (k + d \div k) \div 2$ ，进而得到 $x = t^2 - a_i$ ，若 $x$ 非负则纳入候选集

3. 验证候选x的平方数性

对所有候选x值，逐一统计集合中满足

a_i + x

为完全平方数的元素个数（即平方数性），最终筛选出平方数性最大的x值（若有多个则选择最小的x）。通过以上步骤，可高效缩小x的可能范围，在有限候选集中找到最优解，避免对

0 \leq x \leq 10^{18}

的全域遍历。

Cubes

CPP

#include<algorithm>
#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<queue>
#include<vector>
#include<stack>
#include<map>
#include<set>
#include<ctime>
#include<cstdlib>
#include<cmath>
#define int long long
using namespace std;
int n;
signed main(){
	scanf("%lld",&n);
	for(int i=1;i*i*i<=n;i++){//x-y
		if(n%i) continue;
		int b=n/i;//x*x+x*y+y*y 
		if(b>i*i&&(b-i*i)%3==0){
			int c=(b-i*i)/3;//xy
			int d=i*i+4*c;//(x+y)的平方 
			int sq=sqrt(d);//x+y
			if(sq*sq==d&&(sq-i)%2==0){//答案合法性 
				int y=(sq-i)/2;
				int x=i+y;
				printf("%lld %lld",x,y);
				return 0;
			}
		}
	}
	printf("-1");
	return 0;
}

之前做过，鸣谢123
没啥难度，纯数学硬算，枚举 $x-y=i$ ，通过不断转换求解，注释挺清楚的

8.18模考

赛后总结，本次考试发挥不错，但不能骄傲，继续努力
本次考试感觉思维跳跃性太差，有些思路想不出来，应多练思维题目

小信的铁索连环

CPP

#include<algorithm>
#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<queue>
#include<vector>
#include<stack>
#include<map>
#include<set>
#include<ctime>
#include<cstdlib>
//#include<cmath>
#define pb push_back
using namespace std;
bool f[460][460];
int val[460]; 
int vis[460];
vector <int> g[905]; 
vector <int> vc;
int v,e,ans;
signed main(){
	scanf("%d%d",&v,&e);
	for(int i=1;i<=v;i++){
		scanf("%d",&val[i]);
		ans=max(ans,val[i]);
	}
	for(int i=1;i<=e;i++){
		int x,y;
		scanf("%d%d",&x,&y);
		g[x].pb(y);
		g[y].pb(x);
		f[x][y]=1;
		f[y][x]=1;
	}
	for(int i=1;i<=v;i++){
		for(auto j:g[i]){
			ans=max(ans,val[i]+val[j]);
			for(auto k:g[j]){
				if(f[i][k]==0) continue;
				ans=max(ans,val[i]+val[j]+val[k]);
				for(auto q:g[k]){
					if(f[i][q]==0||f[j][q]==0)	continue;
					ans=max(ans,val[i]+val[j]+val[k]+val[q]);
				}
			}
		}
	}
	printf("%d",ans);
    return 0;
}

这道题搜索没写出来aaa，考试的时候谁能想到4个for啊
题目实际是找最大完全图，首先直接搜肯定过不了，时间复杂度太高了；but题目说了没有相交的边，所以可以推出最多只有四个点（五个点就相交了），所以直接4层for，但还有个问题，如果是 $O(n^4)$ 的话是过不了的，所以应该在每个点的边上枚举，这样就会降很多

两数相等

CPP

#include<algorithm>
#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<queue>
#include<vector>
#include<stack>
#include<map>
#include<set>
#include<ctime>
#include<cstdlib>
#include<cmath>
#define int long long
#define pb push_back
using namespace std;
int t;
int f[65][70][70];
signed main(){
	memset(f,0x3f,sizeof(f));
	f[0][0][0]=0;
	for(int x=1;x<=60;x++){
		for(int q=0;q<=60;q++){
			for(int k=0;k<=60;k++){
				if(q>=x) f[x][q][k]=min(f[x][q][k],f[x-1][q-x][k]+(1ll<<x));
				if(k>=x) f[x][q][k]=min(f[x][q][k],f[x-1][q][k-x]+(1ll<<x));
				f[x][q][k]=min(f[x][q][k],f[x-1][q][k]);
				
			}
		}
	}
	scanf("%lld",&t);
	while(t--){
		int ans=0x7ffffffffffffff;
		int x,y;
		scanf("%lld%lld",&x,&y);
		if(x==y){
			printf("0\n");
		}
		for(int i=0;i<=60;i++){
			for(int j=0;j<=60;j++){
				if((x>>i)==(y>>j)){
					ans=min(ans,f[60][i][j]);
				}
			}
		}
		printf("%lld\n",ans);
	}
	return 0;
}

难……
动态规划， $x \div 2^k$ 的本质就是 $x$ 右移 $k$ 位，花费是 $2^k$ ，就是把 $x$ 和 $y$ 向右移若干位，让他们剩下的数相等
我们先贪心，然后尝试解决,发现贪心会有很多问题，所以就枚举 $x$ 和 $y$ 右移的位数，预处理出花费数组 $f_{i,j,k}$ 表示前 $i$ 个数 $x$ 右移 $j$ 位、 $y$ 右移 $k$ 位的最小花费

碰碰车

CPP

#include<algorithm>
#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<queue>
#include<vector>
#include<stack>
#include<map>
#include<set>
#include<ctime>
#include<cstdlib>
//#include<cmath>
#define pb push_back
using namespace std;
int n,h,w,k,ans=0x7fffffff;
string s[11];
int a[15][15];
map <int,int> m;//状压 
pair<int,int> c[5];
int X[]={0,1,-1,0,0};
int Y[]={0,0,0,1,-1};
void move(int d,int num){
	while(1){
		if(a[c[num].first+X[d]][c[num].second+Y[d]]){
			break;
		}
		c[num].first+=X[d];
		c[num].second+=Y[d];
	}
}
int state(){//状态压缩 
	int sum=0;
	for(int i=1;i<=n;i++){
		sum=sum*10+c[i].first-1;
		sum=sum*10+c[i].second-1;
	} 
	return sum;
} 
void dfs(int step){
	if(c[1]==c[0]){
		ans=min(ans,step);
		return ;
	}
	if(step>=ans||step>k){
		return ;
	}
	int st=state();
	if(m.count(st)&&m[st]<=step){
		return ;
	} 
	m[st]=step;
	for(int i=1;i<=n;i++){
		for(int j=1;j<=4;j++){
			pair<int,int> t=c[i];
			a[c[i].first][c[i].second]=0;
			move(j,i);
			a[c[i].first][c[i].second]=1;
			dfs(step+1);
			a[c[i].first][c[i].second]=0;
			c[i]=t;
			a[c[i].first][c[i].second]=1;
		}
	}
	return ;
}
signed main(){
	memset(a,1,sizeof(a));
	scanf("%d%d%d%d",&n,&h,&w,&k);
	for(int i=1;i<=h;i++){
		for(int j=1;j<=w;j++){
			char x;
			cin>>x;
			if(x=='X'){
				c[0]={i,j};
				a[i][j]=0;
			}
			if(x>='1'&&x<='4'){
				c[x-'0']={i,j};
				a[i][j]=1;
			}
			if(x=='.'){
				a[i][j]=0;
			}
		}
	}
	dfs(0);
	if(ans>k){
		printf("NO SOLUTION");
		return 0;
	}
	printf("%d",ans);
	return 0;
}

真™恶心
没啥，其实就有一个状态压缩，标记哪个点能走，哪些不能

撒谎者的数量

CPP

#include<algorithm>
#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<queue>
#include<vector>
#include<stack>
#include<map>
#include<set>
#include<ctime>
#include<cstdlib>
//#include<cmath>
#define maxx 1000000009//ÓÒ±ß½ç 
#define minn 0//×ó±ß½ç 
using namespace std;
int n,mx;
map <int,int> m;
signed main(){
	scanf("%d",&n);
	for(int i=1;i<=n;i++){
		char op;
		int x;
		cin>>op>>x;
		if(op=='G'){
			m[maxx]--;
			m[x]++;
		} 
		else{
			m[minn]++;
			m[x+1]--;
		}
	}
	int sum=0;
	for(auto i:m){
		sum+=i.second;
		mx=max(mx,sum);
	}
	printf("%d",n-mx);
	return 0;
}

非常简单的差分，没啥好说的

8.19依旧模考

赛时总结，第一题还是一如既往地稳定，不到30min就做完了；第二题感觉很像AT的题，是个思维题，但真想不出来，还得多练
赛后总结

小信玩乐高

CPP

#include<algorithm>
#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<queue>
#include<vector>
#include<stack>
#include<map>
#include<set>
#include<ctime>
#include<cstdlib>
//#include<cmath>
#define pb push_back
using namespace std;
int l,s;
int a,b,n;
int main(){
	//freopen("grq.in","r",stdin);
	//freopen("grq.out","w",stdout);
	scanf("%d%d%d",&b,&a,&n);
	l=a;//长滑块的右
	s=b;//短右
	int i=1;
	for(i=1;l!=n&&s!=n;i++){
		if(l==s){
			l=min(n,l+a-b);
		}
		else{
			s=l;
		} 
	} 
	printf("%d",i); 
	return 0;
}

非常简单的模拟啊，没啥好说的

平方数

CPP

#include<algorithm>
#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<queue>
#include<vector>
#include<stack>
#include<map>
#include<set>
#include<ctime>
#include<cstdlib>
#include<cmath>
#define int long long
#define pb push_back
using namespace std;
int n,a[200005],ans;
vector <int> v;
map <int,int> m;
signed main(){
	freopen("B.in","r",stdin);
	freopen("B.out","w",stdout);
	scanf("%lld",&n);
	for(int i=2;i<=sqrt(200005);i++){
		v.pb(i*i);
	}
	for(int i=1;i<=n;i++){
		scanf("%lld",&a[i]);
		for(int j:v){
			if(a[i]<j) break;
			while(a[i]%j==0) a[i]/=j;
		}
	}
	for(int i=1;i<=n;i++){
		if(a[i]==0){
			ans+=i-1;
			
		}
        else 
    		ans+=m[a[i]]+m[0];
		m[a[i]]++; 
	}
	printf("%lld",ans);
	return 0;
}

平方数的质因数的幂次都是偶数（我真是甜菜），所以两个数的幂次要么都是偶数，要么都是奇数,所以可以直接把偶数次的都除掉，最后就看前面有多少数和你相同
注意如果 $a_i=0$ 那么他和前面所有数都可以，所以算答案需要把0的数量也加上

超时空旅行

CPP

#include<algorithm>
#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<queue>
#include<vector>
#include<stack>
#include<map>
#include<set>
#include<ctime>
#define int long long
#include<cstdlib>
//#include<cmath>
#define pb push_back
using namespace std;
int n,ans=0x7fffffff,m;
vector <int> v;
pair <int,int> c[100005]; 
int vis[100005];
int ma[100005];
signed main(){
	//freopen("grq.in","r",stdin);
	//freopen("grq.out","w",stdout);
	scanf("%lld%lld",&n,&m);
	for(int i=1;i<=n;i++){
		scanf("%lld%lld",&c[i].first,&c[i].second);
	}
	for(int i=1;i<=m;i++){
		scanf("%lld",&ma[i]);
	}
	int w=0;
		for(int i=1;i<n;i++){
			int s=(abs(c[i].first-c[i+1].first)+abs(c[i].second-c[i+1].second));
			int an=0x7fffffff;
			for(int j=1;j<=m;j++){
				int k=ma[j];
				int tmp=(abs(c[k].first-c[i].first)+abs(c[k].second-c[i].second));
				an=min(an,tmp);
			}
			w+=min(an,s);
	printf("%lld",w);
	return 0;
}

~~一开始以为只是动态规划~~
其实这道题就是模拟，每个点有两种情况，走到传送或直接走到下个点，所以for即可
~~代码写的有点臭~~

细胞对战

CPP

#include<algorithm>
#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<queue>
#include<vector>
#include<stack>
#include<map>
#include<set>
#include<ctime>
#include<cstdlib>
//#include<cmath>
#define pb push_back
using namespace std;
int n,ans; 
int val[505][505];
vector <int> a;
vector <int> b;
int vis[505];
signed main(){
	//freopen("grq.in","r",stdin);
	//freopen("grq.out","w",stdout);
	scanf("%d",&n);
	for(int i=1;i<=n;i++){
		for(int j=i+1;j<=n;j++){
			scanf("%d",&val[i][j]);
			val[j][i]=val[i][j]; 
		}
	}
	for(int i=1;i<=n;i++){
		int mx=0,mxs=0;
		for(int j=1;j<=n;j++){
			if(val[i][j]>mx) mxs=mx,mx=val[i][j];
			else if(val[i][j]>mxs) mxs=val[i][j];
		}
		ans=max(mxs,ans);
	}
	printf("1\n%d",ans);
	return 0;
}

~~谁能想到这是个博弈论啊~~
首先对手会把我们的最大值挡掉，所以我们取不了最大值；当对手最大值比我们大时，所以对手也去不到最大值，所以我们可以取最大的次大值，这样就一定赢

结语

鸣谢@WYSY025、@WYSY052、@WYSYXXR 、@HzA_anzi、@Chang__0925 、@a15888206006、 @xmy0726