一场爆零的考试。
记住这个惨痛的教训。
1>心有灵犀
大意：给你一个不超过 10^9 的数字 n 和一个交换次数上限 k，
每次操作对这个 数字 n 的其中两位进行交换，
求出交换后最 大的数字和最小的数字的差的绝对值。
要点：
1. 某一位的数字可以和它本身进行交换
2. 交换的数字不可以有前导零（即第一位不可以是 0）
解法：
1）如果这个数字是 n 位数，那么其交换不超过 n-1 次就可以变成最大值和最小值
可以根据这个点进行剪枝。
2）题目给的数字不超过 10^9，那么进行全排列直接暴力就好了， 时间复杂度最多 9！
我是怎么爆零的：贪心......
以后记得先算最大的时间复杂度，再贪心......
#include<cstdio> #include<cstdlib> #include<iostream> #include<string> #include<algorithm> #include<cstring> using namespace std; string n; int k,len,d[13]; void work() { for(int i=0;i<len;i++) d[i]=n[i]-'0'; sort(d,d+len); int mx=d[len-1]; for(int i=len-2;i>=0;i--) mx=(mx<<3)+(mx<<1)+d[i]; d[len]=0; if(!d[0]) { int pos=1; while(pos<len && !d[pos]) pos++; swap(d[0],d[pos]); } int mn=d[0]; for(int i=1;i<len;i++) mn=(mn<<3)+(mn<<1)+d[i]; printf("%d ",mx-mn); } string ans_mx,ans_mn; void dfs(string nw,int tm,int pos) { if(tm==k) { ans_mx=max(ans_mx,nw); ans_mn=min(ans_mn,nw); return ; } else if(pos>=len) return ; else { ans_mx=max(ans_mx,nw); ans_mn=min(ans_mn,nw); int i=pos; for(int j=i+1;j<len;j++) { if(!i && nw[j]=='0') continue; swap(nw[i],nw[j]); dfs(nw,tm+1,pos+1); swap(nw[i],nw[j]); } dfs(nw,tm,pos+1); } } int main() { int t; cin>>t; while(t--) { cin>>n; scanf("%d",&k); len=n.length() ; if(k>=len-1) work(); else { ans_mn=ans_mx=n; dfs(n,0,0); int ans=0; for(int i=0;i<len;i++) ans=(ans<<3)+(ans<<1)+ans_mx[i]-ans_mn[i]; printf("%d ",ans); } } return 0; }
2>不服来战
你有一列 N 盏灯，初始时有些是开的，有些是关的。
每盏灯有各自的权值。每次操作你可以改变任意连续 K 盏灯的开关状态。
你可以操作任意多次，求最终 最大的 亮着的灯的权值和。
解法：
转换思路：每次改变连续k盏灯，
那么分为操作一次和连着操作两次：
1）改变 i - i+k-1 盏灯的状态
2）改变 i 和 i+k 的状态
然后发现：可以将灯进行分组：
1，1+k，1+k*2，1+k*3...
1，2，2+k，2+k*2...
组与组之间（除了开头与结尾的 两个点 以外）没有影响！
再稍作分析，不难发现，如果一组内“初始时是关的”的灯为偶数个，
那么我们可以 做到只把它们全部打开；
如果一组内“初始时是关的” 的灯为奇数个，这个时候我们不能把所有的灯都打开，只好作出让步，选择放弃亮度最小 的那盏灯。
每一组都如此处理，最后加起来。
关于开头结尾两个点，我们通过枚举 是否在开始时^（1-k）个点的状态，那么最后的点就会随之改变
（其实不太懂这一段）
#include<cstdio> #include<cstdlib> #include<algorithm> using namespace std; int t,n,k,sum; const int N=1003; bool f[N]; int v[N]; int get() { int nw=sum; for(int i=1;i<=k&& i<=n;i++) { bool cnt=false; int mn=2000; for(int j=i;j<=n;j+=k) { if(!f[j]) cnt^=1; mn=min(mn,v[j]); } if(cnt) nw-=mn; } return nw; } int main() { scanf("%d",&t); while(t--) { scanf("%d%d",&n,&k); sum=0,f[n+1]=false,v[n+1]=0; int x; for(int i=1;i<=n;i++) { scanf("%d",&x); if(x) f[i]=true; else f[i]=false; } for(int i=1;i<=n;i++) scanf("%d",&v[i]),sum+=v[i]; int ans=get(); for(int i=1;i<=k;i++) f[i]^=1; ans=max(ans,get()); printf("%d ",ans); } return 0; }
3>铁路网络
等下