首页 > 代码库 > Codeforces Round #283 (Div. 2)
Codeforces Round #283 (Div. 2)
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 23456712 #define mp make_pair13 struct node14 {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 else58 {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)
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。