$NOIP2002$ 题解报告
目录
$Luogu P1031$ 均分纸牌$( √ )$
$Luogu P1032$ 字串变换$( √ )$
$Luogu P1033$ 自由落体$( √ )$
$Luogu P1034$ 矩形覆盖$( √ )$
$Luogu P1031$ 均分纸牌
先算出平均值，然后处理出每堆纸牌与平均值的关系，多了则为$+$，少了为$-$。然后每次把当前这一堆的牌改变，加到下一堆牌里，这样一定是最优的
1 #include<bits/stdc++.h> 2 using namespace std; 3 int a[102]; 4 int main(){ 5 int n,i,ave=0,step=0; 6 cin>>n; 7 for(i=1;i<=n;i++) 8 { 9 cin>>a[i];ave+=a[i]; 10 } 11 ave/=n; 12 for(i=1;i<=n;i++) a[i]-=ave; 13 i=1; 14 int j=n; 15 while(a[i]==0&&i<n) i++; 16 while(a[j]==0&&j>1) j--; 17 while(i<j) 18 { 19 a[i+1]+=a[i]; 20 a[i]=0; 21 step++;i++; 22 while(a[i]==0&&i<j) i++; 23 } 24 cout<<step<<endl; 25 return 0; 26 }
$Luogu P1032$ 字串变换
直接$bfs$，枚举每个转换方式能否匹配，用$map$判重
1 #include<bits/stdc++.h> 2 #define ri register int 3 #define ll long long 4 #define rl register ll 5 #define go(i,a,b) for(ri i=a;i<=b;i++) 6 #define back(i,a,b) for(ri i=a;i>=b;i--) 7 #define g() getchar() 8 #define il inline 9 #define pf printf 10 #define sf scanf 11 #define ull unsigned ll 12 #define mem(a,b) memset(a,b,sizeof(a)) 13 using namespace std; 14 il int fr(){ 15 ri w=0,q=1;char ch=g(); 16 while(ch<'0'||ch>'9'){if(ch=='-')q=-1;ch=g();} 17 while(ch>='0'&&ch<='9')w=(w<<1)+(w<<3)+ch-'0',ch=g(); 18 return w*q; 19 } 20 const int N=42; 21 string A,B,a[10],b[10]; 22 struct node{string s;int t;}p; 23 queue<node> q; 24 map<string,int> vis; 25 int n=1,lena[10],lenb[10]; 26 string change(const string &x,ri i,ri j){ 27 string as=""; 28 if(j+lena[i]>x.length())return as; 29 go(k,0,lena[i]-1)if(x[j+k]!=a[i][k])return as; 30 as=x.substr(0,j); 31 as+=b[i];as+=x.substr(j+lena[i]); 32 return as; 33 } 34 int main(){ 35 freopen("1.in","r",stdin); 36 freopen("1.out","w",stdout); 37 cin>>A>>B;q.push((node){A,0});vis[A]=1; 38 while(cin>>a[n]>>b[n]){lena[n]=a[n].length();lenb[n]=b[n].length();n++;}n--; 39 while(!q.empty()){ 40 p=q.front();q.pop(); 41 if(p.t>10)break; 42 if(p.s==B){pf("%d ",p.t);return 0;} 43 ri len=p.s.length(); 44 go(i,1,n)go(j,0,len-1){ 45 string chg=change(p.s,i,j); 46 if(chg!=""){ 47 node nw;nw.s=chg;nw.t=p.t+1; 48 if(!vis.count(nw.s))q.push(nw),vis[nw.s]=1; 49 } 50 } 51 } 52 puts("NO ANSWER!"); 53 return 0; 54 }