A：暴力弄就好，怎么方便怎么来。
B:我们知道最多加10次，
然后每次加1后我们求能移动的最小值，大概O(N)的效率。
1 #include<bits/stdc++.h> 2 3 using namespace std; 4 #define inf 0x3f3f3f 5 #define N 1234567 6 7 string pan(string s)//求能移动的最小字符串 8 { 9 string tmp=s; 10 for (int i=0;i<s.size();i++) 11 { 12 string k=""; 13 for (int j=i+1;j<s.size();j++) 14 k+=s[j]; 15 for (int j=0;j<=i;j++) 16 k+=s[j]; 17 tmp=min(tmp,k); 18 } 19 return tmp; 20 } 21 22 int main() 23 { 24 int n; 25 cin>>n; 26 string s; 27 28 cin>>s; 29 string ans=s; 30 ans=min(ans,pan(s)); 31 for (int i=0;i<=11;i++) 32 { 33 for (int j=0;j<s.size();j++) 34 { 35 if (s[j]==‘9‘) s[j]=‘0‘; 36 else s[j]+=1; 37 } 38 ans=min(ans,pan(s)); 39 } 40 41 cout<<ans; 42 43 return 0; 44 }
C:其实题目本意是1000*1000的矩阵，改成100*100，就有各种乱过了。
我的做法：先构造一个n*m的矩阵a[n,m];
加入s[i][j]>s[i-1][j] a[i][j]=1;
if (s[i][j]<s[i-1][j]) a[i][j]=-1;
else a[i][j]=0;
具体操作是：如果a[i][j]==-1时，说明其值小于上一行的数，于是这行就改变。去掉。
我们并用一维数组保存状态。
O(n*m)的 效率了
1 #include<bits/stdc++.h> 2 3 using namespace std; 4 #define inf 0x3f3f3f 5 #define N 1234567 6 7 int n,m; 8 string s[1234]; 9 int a[1234][1234]; 10 int b[1234]; 11 12 int main() 13 { 14 cin>>n>>m; 15 for (int i=1;i<=n;i++) cin>>s[i]; 16 for (int i=2;i<=n;i++) 17 { 18 for (int j=0;j<m;j++){ 19 if (s[i][j]>s[i-1][j]) a[i][j+1]=1; 20 else if (s[i][j]<s[i-1][j]) a[i][j+1]=-1; 21 } 22 } 23 24 25 int ans=0; 26 for (int j=1;j<=m;j++) 27 { 28 int flag=0; 29 for (int i=1;i<=n;i++) 30 if (a[i][j]==-1&&b[i]==0)//说明这一行前面比较的状态 31 { 32 flag=1; 33 ans++; 34 break; 35 } 36 if (!flag) 37 { 38 for (int i=1;i<=n;i++) 39 if (a[i][j]==1) b[i]=1; 40 } 41 } 42 43 cout<<ans; 44 45 return 0; 46 }
E:鉴于一直在想E,发现set用法不太会。
其实本省做法也有各种问题。
于是看了前人代码：
大概思路：
先把n,m个问题和人数全加入vector<node>数组
node 记入左区间L，右区间R，还有一个位置pos,以及type类型代表其实询问，还是能选择的人。
自定义排序，以及构造。。
排序的关键是先按L排序，再按type 排序
然后对于是询问我们二分查找在set里面，否侧插入在set中，
还有保存k的状态，如果k==0的话 就从set中删去。
这里用到贪心的方法，前面我们已排好顺序，所以对于询问l[i],r[i],我们查找的时候一定是在L<=l[i]z中找的，
且找的一定是R最接近r[i]的值。这里好好体会一下。
描述的比价混乱：
具体代码应该了解这种思路
1 #include<iostream> 2 #include<stdio.h> 3 #include<string.h> 4 #include<algorithm> 5 #include<string> 6 #include<set> 7 #include<vector> 8 9 using namespace std; 10 typedef long long ll; 11 #define N 234567 12 #define mp make_pair 13 struct node 14 { 15 int l,r,id,type; 16 node(int l=0,int r=0,int id=0,int type=0):l(l),r(r),id(id),type(type){} 17 18 bool operator < (node b)const{ 19 if (l==b.l) return type<b.type; 20 return l<b.l; 21 } 22 }; 23 24 25 int n,m; 26 int lt[N],rt[N]; 27 vector<node> v; 28 int k[N],ans[N]; 29 30 set<pair<int,int> > s; 31 set<pair<int,int> >::iterator it; 32 33 int main() 34 { 35 scanf("%d",&n); 36 for (int i=1;i<=n;i++) 37 { 38 int x,y; 39 scanf("%d%d",&x,&y); 40 v.push_back(node(x,y,i,1)); 41 } 42 43 scanf("%d",&m); 44 for (int i=1;i<=m;i++) 45 { 46 scanf("%d%d%d",<[i],&rt[i],&k[i]); 47 v.push_back(node(lt[i],rt[i],i,0)); 48 49 } 50 51 sort(v.begin(),v.end()); 52 for (int i=0;i<v.size();i++) 53 { 54 if (v[i].type==0) 55 s.insert(mp(v[i].r,v[i].id)); 56 57 else 58 { 59 it=s.lower_bound(mp(v[i].r,0)); 60 if (it==s.end()) 61 { 62 puts("NO"); 63 return 0; 64 } 65 int tmp=it->second; 66 ans[v[i].id]=tmp; 67 s.erase(it); 68 k[tmp]--; 69 if (k[tmp]) s.insert(mp(rt[tmp],tmp)); 70 } 71 72 } 73 puts("YES"); 74 for (int i=1;i<=n;i++) 75 printf("%d ",ans[i]); 76 77 return 0; 78 }
Codeforces Round #283 (Div. 2)
原文：http://www.cnblogs.com/forgot93/p/4173122.html
