http://codeforces.com/contest/1204
第二次rating，时间好晚啊，做了两道就挂机了（还以为会掉很多分，没想到只掉了7分）
每辆火车发车的时刻是4k,k>=0，给出时刻s的二进制表示求s前发车的火车数，找最高位1和次高位1
1 #include<iostream> 2 #include<sstream> 3 #include<fstream> 4 #include<algorithm> 5 #include<cstring> 6 #include<iomanip> 7 #include<cstdlib> 8 #include<cctype> 9 #include<vector> 10 #include<string> 11 #include<cmath> 12 #include<ctime> 13 #include<stack> 14 #include<queue> 15 #include<map> 16 #include<set> 17 #define mem(a,b) memset(a,b,sizeof(a)) 18 #define random(a,b) (rand()%(b-a+1)+a) 19 #define ll long long 20 #define ull unsigned long long 21 #define e 2.71828182 22 #define Pi acos(-1.0) 23 #define ls(rt) (rt<<1) 24 #define rs(rt) (rt<<1|1) 25 #define lowbit(x) (x&(-x)) 26 using namespace std; 27 int read() 28 { 29 int s=1,x=0; 30 char ch=getchar(); 31 while(!isdigit(ch)) {if(ch=='-') s=-1;ch=getchar();} 32 while(isdigit(ch)) {x=10*x+ch-'0';ch=getchar();} 33 return x*s; 34 } 35 int main() 36 { 37 string s,str; 38 cin>>s; 39 int l=s.size(),idx=-1,flag=0; 40 for(int i=0;i<l;++i) 41 { 42 if(s[i]=='1'&&idx==-1) 43 { 44 idx=i;continue; 45 } 46 if(idx!=-1&&s[i]=='1') 47 { 48 flag=1; 49 break; 50 } 51 } 52 if(idx==-1) 53 { 54 cout<<0<<endl;return 0; 55 } 56 int ma=l-idx-1,ans; 57 58 if(ma%2==0) 59 { 60 if(!flag) ans=(ma+2)/2-1; 61 else ans=(ma+2)/2; 62 } 63 else 64 { 65 ans=(ma+1)/2; 66 } 67 cout<<ans<<endl; 68 69 70 }
改：
1 #include<iostream> 2 #include<sstream> 3 #include<fstream> 4 #include<algorithm> 5 #include<cstring> 6 #include<iomanip> 7 #include<cstdlib> 8 #include<cctype> 9 #include<vector> 10 #include<string> 11 #include<cmath> 12 #include<ctime> 13 #include<stack> 14 #include<queue> 15 #include<map> 16 #include<set> 17 #define mem(a,b) memset(a,b,sizeof(a)) 18 #define random(a,b) (rand()%(b-a+1)+a) 19 #define ll long long 20 #define ull unsigned long long 21 #define e 2.71828182 22 #define Pi acos(-1.0) 23 #define ls(rt) (rt<<1) 24 #define rs(rt) (rt<<1|1) 25 #define lowbit(x) (x&(-x)) 26 using namespace std; 27 int read() 28 { 29 int s=1,x=0; 30 char ch=getchar(); 31 while(!isdigit(ch)) {if(ch=='-') s=-1;ch=getchar();} 32 while(isdigit(ch)) {x=10*x+ch-'0';ch=getchar();} 33 return x*s; 34 } 35 int main() 36 { 37 string s,str; 38 cin>>s; 39 int l=s.size(),ans; 40 int idx1=s.find('1',0); 41 int idx2=s.find('1',idx1+1); 42 int ma=l-idx1-1;//最高位1 43 if(idx1==-1) return 0*printf("%d",0); 44 if(ma%2==0&&idx2==-1) ans=(ma+2)/2-1; 45 else ans=(ma+2)/2; 46 cout<<ans<<endl; 47 }
简单的贪心。
1 #include<iostream> 2 #include<sstream> 3 #include<fstream> 4 #include<algorithm> 5 #include<cstring> 6 #include<iomanip> 7 #include<cstdlib> 8 #include<cctype> 9 #include<vector> 10 #include<string> 11 #include<cmath> 12 #include<ctime> 13 #include<stack> 14 #include<queue> 15 #include<map> 16 #include<set> 17 #define mem(a,b) memset(a,b,sizeof(a)) 18 #define random(a,b) (rand()%(b-a+1)+a) 19 #define ll long long 20 #define ull unsigned long long 21 #define e 2.71828182 22 #define Pi acos(-1.0) 23 #define ls(rt) (rt<<1) 24 #define rs(rt) (rt<<1|1) 25 #define lowbit(x) (x&(-x)) 26 using namespace std; 27 int read() 28 { 29 int s=1,x=0; 30 char ch=getchar(); 31 while(!isdigit(ch)) {if(ch=='-') s=-1;ch=getchar();} 32 while(isdigit(ch)) {x=10*x+ch-'0';ch=getchar();} 33 return x*s; 34 } 35 int main() 36 { 37 int n=read(),l=read(),r=read(); 38 39 int ans=(1<<l)-1; 40 int mn=ans+n-l; 41 42 ans=(1<<r)-1; 43 int ma=ans+(n-r)*((1)<<(r-1)); 44 45 cout<<mn<<' '<<ma<<endl; 46 47 }
图论不补，存下大佬代码
1 #include <bits/stdc++.h> 2 #define fi first 3 #define se second 4 #define pb push_back 5 using namespace std; 6 typedef long long ll; 7 8 #define n 105 9 10 ll dist[n][n]; 11 12 int main() { 13 int N; 14 cin >> N; 15 for(int i = 1; i <= N; i++) { 16 for(int j = 1; j <= N; j++) { 17 char a; 18 cin >> a; 19 // cout << a << " "; 20 //if(a == '1') cout << "halo gan "; 21 if(a == '1') dist[i][j] = 1; 22 else if(i == j) dist[i][j] = 0; 23 else dist[i][j] = 1e9; 24 // cin >> dist[i][j]; 25 } 26 } 27 28 for(int k = 1; k <= N; k++) { 29 for(int i = 1; i <= N; i++) { 30 for(int j = 1; j <= N; j++) { 31 // cout << "a"; 32 if(dist[i][k] + dist[k][j] < dist[i][j]) { 33 dist[i][j] = dist[i][k] + dist[k][j]; 34 } 35 } 36 } 37 } 38 39 vector<int> ans; 40 int K; 41 cin >> K; 42 43 int x[K+5]; 44 for(int i = 1; i <= K; i++) { 45 cin >> x[i]; 46 } 47 48 49 int prev = -1; 50 for(int i = 1; i < K; i++) { 51 int a = x[i], b = x[i + 1]; 52 if(i == 1) { 53 prev = a; 54 ans.pb(prev); 55 } 56 else { 57 //cout << dist[prev][a] << " " << dist[a][b] << " " << dist[prev][b] << " "<< prev << " " << a << " " << b << " "; 58 if(dist[prev][a] + dist[a][b] == dist[prev][b]) { 59 continue; 60 } 61 else { 62 prev = a; 63 ans.pb(prev); 64 } 65 } 66 } 67 ans.pb(x[K]); 68 cout << ans.size() << " "; 69 70 for(int i = 0 ; i < ans.size(); i++) { 71 if(i != 0) cout << " "; 72 cout << ans[i]; 73 } 74 75 cout << " "; 76 77 78 }
D、Kirk and a Binary String (hard version)
给定一个01串s，求01串t，使得：1、t的任意区间内的最长非递减子序列长度和s的对应区间内的最长非递减子序列长度相等；2、t串中包含0的个数尽可能多。
也就是尽可能的将s串中的0换成1
将10、1100、1010这样的除去，剩下的1改为0就行了
1 #include<iostream> 2 #include<sstream> 3 #include<fstream> 4 #include<algorithm> 5 #include<cstring> 6 #include<iomanip> 7 #include<cstdlib> 8 #include<cctype> 9 #include<vector> 10 #include<string> 11 #include<cmath> 12 #include<ctime> 13 #include<stack> 14 #include<queue> 15 #include<map> 16 #include<set> 17 #define mem(a,b) memset(a,b,sizeof(a)) 18 #define random(a,b) (rand()%(b-a+1)+a) 19 #define ll long long 20 #define ull unsigned long long 21 #define e 2.71828182 22 #define Pi acos(-1.0) 23 #define P pair<int,int> 24 #define ls(rt) (rt<<1) 25 #define rs(rt) (rt<<1|1) 26 #define lowbit(x) (x&(-x)) 27 using namespace std; 28 int read() 29 { 30 int s=1,x=0; 31 char ch=getchar(); 32 while(!isdigit(ch)) {if(ch=='-') s=-1;ch=getchar();} 33 while(isdigit(ch)) {x=10*x+ch-'0';ch=getchar();} 34 return x*s; 35 } 36 int main() 37 { 38 string str;cin>>str; 39 int l=str.size(); 40 stack< P > buf; 41 for(int i=0;i<l;++i) 42 if(str[i]=='0'&&!buf.empty()&&buf.top().first==1) buf.pop(); 43 else buf.push(make_pair(str[i]-'0',i)); 44 while(!buf.empty()) 45 { 46 if(buf.top().first==1) str[buf.top().second]='0'; 47 buf.pop(); 48 } 49 cout<<str<<endl; 50 return 0; 51 }