第一次发题解瑟瑟发抖 Σ(?д?;)
给自己定个目标，一周至少发一篇区域赛题解，争取再发一篇网络赛或者 CF div2+ 题解
更新中！！！题号下没有题解的就是还没做出来的 Σ(?д?;)
题意简述：田忌赛马，给出双方马的速度，赢一局得200铜钱，求最多得多少铜钱。
一开始按照题意想的二分图，后来发现是贪心 Σ(?д?;)
先把国王的马和田忌的马排序，塞进一个deque里
然后按照以下方法操作：
(1) 若田忌最快的马比国王最快的马快，则用田忌最快的马赢国王最快的马。
设国王最快的马为 k ，田忌最快的马为 t ，且各有另一只马 k‘, t‘
有 k‘ ≤ k < t , t‘ ≤ t
如果让 k 和 t‘ 比，k‘ 和 t 比
a. t‘ ≤ k‘ 时，原来一胜一负/平，交换后一胜一负。
b. k‘ < t‘ ≤ k 时，原来两胜，交换后一胜一负/平。
c. t‘ > k 时，原来两胜，交换后两胜。
因此交换不会使结果更优，得证。
(2) 若田忌最快的马比国王最快的马慢，则用田忌最慢的马输国王最快的马。
因为无论用什么马跟国王的这只马比都会输，因此消耗掉己方最慢的马最优。
(3) 若田忌最快的马和国王的马一样快，且田忌最慢的马比国王最慢的马快，则用田忌最慢的马赢国王最慢的马。
设国王最快的马为 k ，田忌最快的马为 t ，且各有另一只马 k‘, t‘
有 k < t ≤ t‘ , k ≤ k‘
如果让 k 和 t‘ 比，k‘ 和 t 比
a. k‘ ≤ t 时，原来两胜，交换后一胜一平。
b. t < k‘ ≤ t‘ 时，原来两胜/一胜一平，交换后一胜一负
c. k‘ > t 时，原来一胜一负，交换后一胜一负
因此交换不会使结果更优，得证。
(4) 若田忌最快的马和国王的马一样快，且田忌最慢的马比国王最慢的马慢或一样快，则用田忌最慢的马输国王最快的马。
设国王最快的马为 k ，田忌最慢的马为 t ，且各有另一只马 k‘, t‘
有 t ≤ k‘ ≤ k , t ≤ t‘ ≤ k
如果让 k 和 t‘ 比，k‘ 和 t 比
a. k‘ ≤ t‘ 时，原来两负或一负一平，交换后两负。
c. k‘ > t‘ 时，原来一胜一负，交换后两负。
因此交换不会使结果更优，得证。
其实以上的证明并不严格，因为除了交换还能三轮换、四轮换，可能那样会使得结果更优，但是emmm... 这个结论是正确的（逃
时间复杂度O(n)
AC代码：
#include <cstdio> #include <algorithm> using namespace std; typedef long long ll; int king[10010],tj[10010],ans=0; void comp(int t,int k){ if(t<k) ans--; else if(t>k) ans++; } int cmp(int a,int b){ return a>b; } int main(){ int n,tfp,tep,kfp,kep; while(scanf("%d",&n)!=EOF&&n!=0){ for(int i=0;i<n;i++){ scanf("%d",&tj[i]); } for(int i=0;i<n;i++){ scanf("%d",&king[i]); } sort(tj,tj+n,cmp); sort(king,king+n,cmp); tfp=kfp=ans=0; tep=kep=n-1; for(int i=0;i<n;i++){ if(tj[tfp]<king[kfp]) {comp(tj[tep],king[kfp]); --tep,++kfp;} else if(tj[tfp]>king[kfp]) {comp(tj[tfp],king[kfp]); ++tfp,++kfp;} else if(tj[tep]>king[kep]) {comp(tj[tep],king[kep]); --tep,--kep;} else {comp(tj[tep],king[kfp]); --tep,++kfp;} } printf("%d\n",ans*200); } return 0; }
题意简述：求从m到n中0-9各出现了多少次。
简单的数位dp，dp[i]表示i位数中1-9的个数以及带前导零的i位数中0的个数，dp0[i]表示不带前导零的i位数中0的个数，转移方程
dp[i]=dp[i-1]*10+10^(i-1)
dp0[i]=dp0[i-1]+dp[i-1]*9
时间复杂度大概是O(log n + log m)
AC代码：
#include <cstdio> #include <algorithm> using namespace std; typedef long long ll; int dp[10],dp0[10],ans1[10],ans2[10],temp[10]; int pow(int a,int n){ ll ans=1; for(int i=0;i<n;i++) ans*=a; return ans; } void init(){ for(int i=1;i<10;i++){ dp[i]=dp[i-1]*10+pow(10,i-1); dp0[i]=dp0[i-1]+dp[i-1]*9; } } void solve(int n,int *arr){ int dptr=1,cnt=0,flag=1; while(n/dptr>=10){ ++cnt; dptr*=10; } arr[0]=dp0[cnt]; for(int j=1;j<10;j++) arr[j]=dp[cnt]; while(dptr){ for(int i=flag;i<n/dptr;i++){ arr[i]+=dptr; for(int i=0;i<10;i++) arr[i]+=dp[cnt]; } flag=0; arr[n/dptr]+=n%dptr; n%=dptr; dptr/=10; --cnt; } } int main(){ init(); int a,b; while(scanf("%d%d",&a,&b)==2&&a!=0){ if(a>b) swap(a,b); solve(b+1,ans1); solve(a,ans2); for(int i=0;i<10;i++) printf("%d%c",ans1[i]-ans2[i],i==9?‘\n‘:‘ ‘); } return 0; }
题意简述：不好概括。。。看原题吧
用迭代加深搜索 IDDFS 可解，由于一步最多只能向中心移入一个目标数字，所以搜索最大深度减去当前深度小于中心非目标数字块的数量时剪枝。
用常量数组可以大幅简化代码，还有注意要找字典序最小的，所以搜到结果不要马上退出，要再看其他的数字会不会有字典序更小的。
复杂度是 O(8^n) ， n 是答案也就是搜索深度，看起来很大但是有剪枝所以还是能过
#include <cstdio> #include <algorithm> #include <cstring> using namespace std; typedef long long ll; //////////LOCALS////////// #ifdef OFFLINE int unused_variable_name=(freopen("in.txt","r",stdin),1); #endif //////////LOCALS////////// int arr[24],route[100],route2[100]; const int rots[8][7]={ {0,2,6,11,15,20,22}, {1,3,8,12,17,21,23}, {10,9,8,7,6,5,4}, {19,18,17,16,15,14,13}, {23,21,17,12,8,3,1}, {22,20,15,11,6,2,0}, {13,14,15,16,17,18,19}, {4,5,6,7,8,9,10}, }; const int rev[8]={5,4,7,6,1,0,3,2}; const int ctr[8]={6,7,8,11,12,15,16,17}; void mkmove(int n){ int temp=arr[rots[n][0]]; for(int i=1;i<7;i++){ arr[rots[n][i-1]]=arr[rots[n][i]]; } arr[rots[n][6]]=temp; } int countctr(int n){ int ans=0; for(int i=0;i<8;i++) if(arr[ctr[i]]==n) ++ans; return ans; } void print(){ printf(" %d %d \n",arr[0],arr[1]); printf(" %d %d \n",arr[2],arr[3]); for(int i=4;i<11;i++) printf("%d",arr[i]); printf("\n %d %d \n",arr[11],arr[12]); for(int i=13;i<20;i++) printf("%d",arr[i]); printf("\n %d %d \n",arr[20],arr[21]); printf(" %d %d \n\n",arr[22],arr[23]); } bool iddfs(int n,int dep,int limit){ int cnt=countctr(n); bool flag=false; if(cnt==8) return true; if(8-cnt>limit-dep) return false; for(int i=0;i<8;i++){ route[dep]=i; mkmove(i); if(iddfs(n,dep+1,limit)) flag=true; mkmove(rev[i]); if(flag) return true; } return false; } bool cmproute(int l){ for(int i=0;i<l;i++){ if(route[i]<route2[i]) return true; if(route[i]>route2[i]) return false; } return false; } int main(){ int ans=-1,ansn; while(scanf("%d",&arr[0])!=EOF&&arr[0]!=0){ ans=-1; for(int i=1;i<24;i++){ scanf("%d",&arr[i]); } //print(); for(int j=0;;j++){ for(int k=1;k<4;k++){ //printf("%d %d\n",k,j); if(iddfs(k,0,j)){ if(ans==-1){ //printf("ok!\n"); memcpy(route2,route,sizeof(route)); ans=j; ansn=k; } else { //printf("try replace\n"); if(cmproute(ans)){ memcpy(route2,route,sizeof(route)); ansn=k; //printf("ok!\n"); } } } } if(ans!=-1) break; } for(int i=0;i<ans;i++) printf("%c",route2[i]+‘A‘); if(ans==0) printf("No moves needed"); printf("\n%d\n",ansn); } return 0; }
时限15000ms，这个代码327ms
预计下次更新 South America 2006, Brazil Subregion （POJ 3112 - 3119)
2004上海区域赛 Asia Regional Shanghai 题解
原文：https://www.cnblogs.com/whatss7/p/12759558.html