这套题没有算法性特别强的题，主要强调理清题意后的分析观察题目特性的能力，用到的都是常用的技巧。最后两道比较考代码能力。
A. Vitaliy and Pie
扫一遍字符串，拿到的钥匙记上，遇到开不了的门就ans++.
#include<iostream> #include<cstdio> #include<cstdlib> #include<cstring> #include<string> #include<cmath> #include<map> #include<set> #include<list> #include<deque> #include<vector> #include<algorithm> #include<stack> #include<queue> #include<cctype> #include<sstream> using namespace std; #define pii pair<int,int> #define LL long long int const double eps=1e-10; const int INF=1000000000; const int maxn=100000+10; int n,ans=0; string s; int a[26]; int main() { //freopen("in2.txt","r",stdin); //freopen("out.txt","w",stdout); scanf("%d",&n); cin>>s; int len =s.length(); memset(a,0,sizeof(a)); for(int i=0;i<len;i++) { if(s[i]>='a'&&s[i]<='z') { a[s[i]-'a']++; } else { char c=s[i]-'A'+'a'; if(a[c-'a']==0) { ans++; } else { a[c-'a']--; } } } cout<<ans<<endl; //fclose(stdin); //fclose(stdout); return 0; }
B. Pasha and String
根据m<=105，如果每次都真的交换一下，那么必然超时。那么需要分析问题找特性了，首先这种交换问题很显然的特点就是最终交换次数为偶数等于没换，交换次数为奇数等于换了一次。那么只要用一个数组a[i]统计一下每个s[i]的最终交换次数，最后扫一遍数组，奇数的换就行了。记录s[i]的交换次数又有技巧，如果m次中每次都把a[t]到a[|s|-t+1]都加1，那么这又会超时，所以采用线性数组区间加减常用的延迟技巧，可以把时间降到线性。也就是每次只是a[t]++,最后扫一遍把所有a[i]都变了就好了。由于题目特点，只需要算一半。
#include<iostream> #include<cstdio> #include<cstdlib> #include<cstring> #include<string> #include<cmath> #include<map> #include<set> #include<list> #include<deque> #include<vector> #include<algorithm> #include<stack> #include<queue> #include<cctype> #include<sstream> using namespace std; #define pii pair<int,int> #define LL long long int const double eps=1e-10; const int INF=1000000000; const int maxn=100000+10; char s[2*maxn]; int m,a[maxn]; int main() { //freopen("in2.txt","r",stdin); scanf("%s",s); scanf("%d",&m); int t,len=strlen(s); for(int i=0; i<m; i++) { scanf("%d",&t); a[t]++; } int tt=len/2; for(int i=1; i<=tt; i++) a[i]+=a[i-1]; for(int i=1; i<=tt; i++) { if(a[i]&1) swap(s[i-1],s[len-i]); } puts(s); return 0; }
C. Ilya and Sticks
贪心，能用大的就用大的呗。之前先处理一下，把奇数个的减一，后面有比它小1的就加到后边。
#include<iostream> #include<cstdio> #include<cstdlib> #include<cstring> #include<string> #include<cmath> #include<map> #include<set> #include<list> #include<deque> #include<vector> #include<algorithm> #include<stack> #include<queue> #include<cctype> #include<sstream> using namespace std; #define pii pair<int,int> #define LL long long int const double eps=1e-10; const int INF=1000000000; const int maxn=100000+10; int n,l,maxl=-1; LL ans=0; int cnt[10*maxn]; int main() { //freopen("in2.txt","r",stdin); scanf("%d",&n); for(int i=0; i<n; i++) { scanf("%d",&l); cnt[l]++; maxl=max(maxl,l); } for(int i=maxl; i>=1; i--) { if(cnt[i]&1) { if(cnt[i-1]>0) { cnt[i-1]++; cnt[i]--; } else cnt[i]--; } } for(int i=maxl; i>=1; i--) { while(cnt[i]>=4) { ans+=(LL)i*i; cnt[i]-=4; } if(cnt[i]==2) { for(int j=i-1; j>=1; j--) { if(cnt[j]>=2) { ans+=(LL)i*j; //cnt[i]-=2; cnt[j]-=2; i=j+1; break; } } } } cout<<ans<<endl; return 0; }
D. Arthur and Walls
观察，分析题目特点很重要。这道题的特性就是在每个2*2的子单元里出现四个点一个星，那么这个星必删，其它情况的星都可以不删。相关题目做多了的大牛其实会很快找到这种规律。还要注意有可能当前删一个星后影响到前面本来不用删的星变成了必删的星了，所以每删一次dfs检查一下。
#include<iostream> #include<cstdio> #include<cstdlib> #include<cstring> #include<string> #include<cmath> #include<map> #include<set> #include<list> #include<deque> #include<vector> #include<algorithm> #include<stack> #include<queue> #include<cctype> #include<sstream> using namespace std; #define pii pair<int,int> #define LL long long int const double eps=1e-10; const int INF=1000000000; const int maxn=2000+10; int n,m; char s[maxn][maxn]; int dx[8]= {0,0,1,-1,1,-1,-1,1}; int dy[8]= {1,-1,1,-1,0,0,1,-1}; bool ok(int x,int y) { return (x>=1&&x<=n)&&(y>=1&&y<=m); } bool gao(int x,int y) { if(ok(x,y+1)&&ok(x+1,y)&&ok(x+1,y+1)) { if(s[x][y+1]=='.'&&s[x+1][y]=='.'&&s[x+1][y+1]=='.') return true; } if(ok(x-1,y+1)&&ok(x-1,y)&&ok(x,y+1)) { if(s[x-1][y+1]=='.'&&s[x-1][y]=='.'&&s[x][y+1]=='.') return true; } if(ok(x-1,y-1)&&ok(x-1,y)&&ok(x,y-1)) { if(s[x-1][y-1]=='.'&&s[x-1][y]=='.'&&s[x][y-1]=='.') return true; } if(ok(x+1,y-1)&&ok(x,y-1)&&ok(x+1,y)) { if(s[x+1][y-1]=='.'&&s[x][y-1]=='.'&&s[x+1][y]=='.') return true; } return false; } void dfs(int x,int y) { if(s[x][y]=='.') return; if(gao(x,y)) { s[x][y]='.'; for(int i=0; i<8; i++) { int tx=x+dx[i]; int ty=y+dy[i]; if(ok(tx,ty)) { if(s[tx][ty]=='*') { dfs(tx,ty); } } } return ; } else return ; } int main() { //freopen("in2.txt","r",stdin); //freopen("out.txt","w",stdout); scanf("%d%d",&n,&m); for(int i=1; i<=n; i++) { scanf("%s",s[i]+1); } for(int i=1; i<=n; i++) { for(int j=1; j<=m; j++) { if(s[i][j]=='*') { dfs(i,j); } } } for(int i=1; i<=n; i++) puts(s[i]+1); //fclose(stdin); //fclose(stdout); return 0; }
E. Anya and Cubes
中途相遇法的典型应用。直接枚举是325的复杂度会超时，那么分两头枚举呗，每头312这样就不超时了。但是具体实现需要一定的代码功力。这里引用网上某大神的代码，比我写的好。
#include <vector> #include <list> #include <map> #include <string> #include <set> #include <cstring> #include <deque> #include <queue> #include <stack> #include <bitset> #include <algorithm> #include <functional> #include <numeric> #include <utility> #include <sstream> #include <iostream> #include <iomanip> #include <cstdio> #include <cmath> #include <cstdlib> #include <ctime> using namespace std; typedef long long LL; typedef unsigned long long ULL; map <LL, int> q1[30], q2[30]; LL a[30] = {0}, gc[30] = {0}; int n, k; LL s; int dfs(int wh, int end_, int t, int one, LL sum) { if(t > k || sum > s) return 0; if(wh == end_+1) { if(one == 1) q1[t][sum]++; else for(int i = t; i <= k; i++) q2[i][sum]++;// return 0; } dfs(wh+1, end_, t, one, sum+a[wh]); if(a[wh] < 19) dfs(wh+1, end_, t+1, one, sum+gc[a[wh]]); dfs(wh+1, end_, t, one, sum); } int main () { gc[0] = 1; gc[1] = 1; for(int i = 2; i <= 19; i++) gc[i] = gc[i-1]*i; cin >> n >> k >> s; int mid = n/2; for(int i = 1; i <= n; i++) cin >> a[i]; dfs(1, mid, 0, 1, 0); dfs(mid+1, n, 0, 2, 0); map <LL, int> :: iterator it; LL ans = 0; for(int i = 0; i <= k; i++) { for(it = q1[i].begin(); it != q1[i].end(); it++) { if(q2[k-i].find(s - (it->first)) != q2[k-i].end()) ans += (LL)(it->second)*q2[k-i][s- (it->first)]; } } cout << ans << endl; return 0; }