@AlanWong
2016-12-08T16:47:36.000000Z
字数 10922
阅读 924
A.Design Tutorial: Learn from Math
题意：
给出一个整数n，12 ≤ n ≤ 1e6，输出两个合数a和b，使a+b=n。
思路：
这题很水，既然最小值为12，那么就对n分奇偶讨论，若为偶数，则n-4一定也是偶数，所以输出4和n-4；若为奇数，那么n-9一定是大于2的偶数，输出9和n-9。
代码：
#include <bits/stdc++.h>#include <functional>#include <algorithm>#include <iostream>#include <cstring>#include <cstdlib>#include <utility>#include <sstream>#include <complex>#include <cstdio>#include <bitset>#include <vector>#include <cmath>#include <queue>#include <stack>#include <ctime>#include <list>#include <set>#include <map>using namespace std;#define ll long long#define ull unsigned long longconst int MAXN=100005;const int INF=0x3f3f3f3f;const int MOD=1000000007;int main(){//freopen("in.txt","r",stdin);//freopen("out.txt","w",stdout);int n;while(~scanf("%d", &n)){if(n%2) printf("%d 9\n", n-9);else printf("%d 4\n", n-4);}return 0;}
B.Design Tutorial: Learn from Life
题意：
n个人在一楼，一个最大载k人的电梯将他们载到他们要去的楼层，上下电梯时间忽略不计，运行时间为楼层差。问将他们全部送到指定楼层要多久。
思路：
这题很水，先排序，从高往低送，纯模拟。
代码：
#include <bits/stdc++.h>#include <functional>#include <algorithm>#include <iostream>#include <cstring>#include <cstdlib>#include <utility>#include <sstream>#include <complex>#include <cstdio>#include <bitset>#include <vector>#include <cmath>#include <queue>#include <stack>#include <ctime>#include <list>#include <set>#include <map>using namespace std;#define ll long long#define ull unsigned long longconst int MAXN=100005;const int INF=0x3f3f3f3f;const int MOD=1000000007;int n, k, ans;int arr[2005];int main(){//freopen("in.txt","r",stdin);//freopen("out.txt","w",stdout);scanf("%d %d", &n, &k);for(int i=0; i<n; i++)scanf("%d", &arr[i]);sort(arr, arr+n);n--;while(n>=0){ans+=2*(arr[n]-1);n-=k;}printf("%d\n", ans);return 0;}
C.Design Tutorial: Make It Nondeterministic
题意：
n个人用自己的姓氏或名字作为自己用户名，若按照字典序排序，是否有一种方案使这些人按照给出顺序排序。
思路：
这题难点应该在读题，给出的数列的每一位Pi指的是名字原来所在的位置现在排在i位。设置中间string变量s记录上一个选择的名字，然后按之前记录位置的pos数组依次遍历当前的名字能否满足字典序大于s，优先选择字典序小的名字来判断，任一不满足的循环节即跳出。
代码：
#include <bits/stdc++.h>#include <functional>#include <algorithm>#include <iostream>#include <cstring>#include <cstdlib>#include <utility>#include <sstream>#include <complex>#include <cstdio>#include <bitset>#include <vector>#include <cmath>#include <queue>#include <stack>#include <ctime>#include <list>#include <set>#include <map>using namespace std;#define ll long long#define ull unsigned longconst int MAXN=100005;const int INF=0x3f3f3f3f;const int MOD=1000000007;int N;struct node{string fn, ln;}name[100005];string s;int pos[100005];int main(){//freopen("in.txt","r",stdin);//freopen("out.txt","w",stdout);cin>>N;for(int i=1; i<=N; i++){cin>>name[i].fn>>name[i].ln;if(name[i].fn>name[i].ln) swap(name[i].fn, name[i].ln);}for(int i=1; i<=N; i++)cin>>pos[i];bool flag=true;for(int i=1; i<=N; i++){int cur=pos[i];if(s<name[cur].fn){s=name[cur].fn;continue;}if(s<name[cur].ln){s=name[cur].ln;continue;}flag=false;break;}if(flag) cout<<"YES"<<endl;else cout<<"NO"<<endl;return 0;}
E.MUH and Sticks
题意：
给出六个棍子的长度，如果四个等长，剩下两个长度不等为Bear，相等为Elephant，否则为Alien。
思路：
这题很水，直接上代码。
代码：
#include <bits/stdc++.h>#include <functional>#include <algorithm>#include <iostream>#include <cstring>#include <cstdlib>#include <utility>#include <sstream>#include <complex>#include <cstdio>#include <bitset>#include <vector>#include <cmath>#include <queue>#include <stack>#include <ctime>#include <list>#include <set>#include <map>using namespace std;#define ll long long#define ull unsigned long longconst int MAXN=100005;const int INF=0x3f3f3f3f;const int MOD=1000000007;int arr[20];int len, flag;bool cmp(int a, int b){return a>b;}int main(){//freopen("in.txt","r",stdin);//freopen("out.txt","w",stdout);for(int i=0; i<6; i++){cin>>len;arr[len]++;}sort(arr, arr+10, cmp);if(arr[0]==4){if(arr[1]==1) cout<<"Bear"<<endl;else cout<<"Elephant"<<endl;}else if(arr[0]==5) cout<<"Bear"<<endl;else if(arr[0]==6) cout<<"Elephant"<<endl;else cout<<"Alien"<<endl;return 0;}
F.MUH and Important Things
题意：
给出长度为n的数列，问能否有三种以上的非递减排序，有，输出“YES”并输入任意三种满足要求的不同排列；没有输出“NO”。
思路：
分情况，若有三个相同数字或者两对分别相同的数字即满足条件，暴力遍历打印呗。
代码：
#include <bits/stdc++.h>#include <functional>#include <algorithm>#include <iostream>#include <cstring>#include <cstdlib>#include <utility>#include <sstream>#include <complex>#include <cstdio>#include <bitset>#include <vector>#include <cmath>#include <queue>#include <stack>#include <ctime>#include <list>#include <set>#include <map>using namespace std;#define ll long long#define ull unsigned long longconst int MAXN=2005;const int INF=0x3f3f3f3f;const int MOD=1e9+7;int n;int now, pp[2];struct node{int p, pos;}num[MAXN];bool cmp(node a, node b){return a.p<b.p;}void swp(node &a, node &b){node t;t.p=a.p;t.pos=a.pos;a.p=b.p;a.pos=b.pos;b.p=t.p;b.pos=t.pos;}void prt(){cout<<num[1].pos;for(int i=2; i<=n; i++){cout<<' '<<num[i].pos;}cout<<endl;}int main(){//freopen("in.txt","r",stdin);//freopen("out.txt","w",stdout);cin>>n;for(int i=1; i<=n; i++){cin>>num[i].p;num[i].pos=i;}sort(num+1, num+n+1, cmp);bool flag=false;for(int i=n; i>2; i--){if(num[i].p==num[i-1].p && num[i-1].p==num[i-2].p){cout<<"YES\n";prt();swp(num[i], num[i-1]);prt();swp(num[i], num[i-2]);prt();return 0;}else if(num[i].p==num[i-1].p){pp[now++]=i;if(flag) break;flag=true;}}if(pp[0] && num[2].p==num[1].p){pp[1]=2;}if(pp[1]){cout<<"YES\n";prt();swp(num[pp[0]], num[pp[0]-1]);prt();swp(num[pp[1]], num[pp[1]-1]);prt();}else{cout<<"NO\n";}return 0;}
G.MUH and House of Cards
题意：
用恰好n（1<=n<=10^12）张卡片搭建一个房子，问能搭建多少种不同的高度的房子。
搭建的房子满足以下要求：
1.每一层的房子数要多于他上面那层的房子数。
2.同一层的房子必须是连续的。
3.大于两间的房子要有天花板。
思路：
找规律撒，每行去掉两个就能整除3。从第一层网上遍历跑呗，用t记录加1层至少要多少建材。
代码：
#include <bits/stdc++.h>#include <functional>#include <algorithm>#include <iostream>#include <cstring>#include <cstdlib>#include <utility>#include <sstream>#include <complex>#include <cstdio>#include <bitset>#include <vector>#include <cmath>#include <queue>#include <stack>#include <ctime>#include <list>#include <set>#include <map>using namespace std;#define ll long long#define ull unsigned long longconst int MAXN=100005;const int INF=0x3f3f3f3f;const int MOD=1e9+7;ll N, ans;int main(){//freopen("in.txt","r",stdin);//freopen("out.txt","w",stdout);cin>>N;for(ll i=2, t=2; t<=N; i++){if((N-t)%3==0) ans++;t=i*(3*i+1)/2;}cout<<ans<<endl;return 0;}
I.George and Accommodation
题意：
给定n（1<=n<=100）,n个房间的容量q和已入住人数p（0<=pi<=qi<=100），问有多少个房间能满足两人围炉夜话，深夜交♂流哲♂学的愿望。
思路：
一个房间一个房间考察清楚呗，然后嘿嘿嘿。。。
代码：
#include <bits/stdc++.h>#include <functional>#include <algorithm>#include <iostream>#include <cstring>#include <cstdlib>#include <utility>#include <sstream>#include <complex>#include <cstdio>#include <bitset>#include <vector>#include <cmath>#include <queue>#include <stack>#include <ctime>#include <list>#include <set>#include <map>using namespace std;#define ll long long#define ull unsigned long longconst int MAXN=100005;const int INF=0x3f3f3f3f;const int MOD=1e9+7;int n;int p, q;int ans;int main(){//freopen("in.txt","r",stdin);//freopen("out.txt","w",stdout);cin>>n;while(n--){cin>>p>>q;if(q-p>1) ans++;}cout<<ans<<endl;return 0;}
J.Fedor and New Game
题意：
给定m（1<=m<=1000）和n(1<=n<=20),给定m个整数x（0<=xi<=2^n-1）描述了m个玩家的兵种情况，给定一个整数X描述了主人公的兵种情况。
兵种情况的描述方式：以二进制考虑，第0到第n-1位分别表示该玩家是否拥有当前兵种。
给定k（1<=k<=n）,当两名玩家的兵种情况的差异不超过k，这两名玩家可以成为好朋友。问主人公可以和多少名玩家成为好朋友。
思路：
两层循环暴力跑呗，判断可以用位运算比较每一位是否相同。
代码：
#include <bits/stdc++.h>#include <functional>#include <algorithm>#include <iostream>#include <cstring>#include <cstdlib>#include <utility>#include <sstream>#include <complex>#include <cstdio>#include <bitset>#include <vector>#include <cmath>#include <queue>#include <stack>#include <ctime>#include <list>#include <set>#include <map>using namespace std;#define ll long long#define ull unsigned long longconst int MAXN=100005;const int INF=0x3f3f3f3f;const int MOD=1e9+7;int n, m, k, flag, now, ans;int num[1005];int main(){//freopen("in.txt","r",stdin);//freopen("out.txt","w",stdout);cin>>n>>m>>k;for(int i=0; i<m; i++)cin>>num[i];cin>>flag;for(int i=0; i<m; i++){now=0;for(int j=0; j<n; j++)if((num[i]&(1<<j)) != (flag&(1<<j))) now++;if(now<=k) ans++;}cout<<ans<<endl;return 0;}
K.George and Job
题意：
给定一个长度为n的整数序列p，给m和k让你在序列p中选择不重合的m段长度为k的子段，求这m*k个数的和的最大值。
思路：
DP，最怕DP，看了题解才会做。用一个sum[i]数组存前i项的和。二维DP数组dp[i][j]表示前i位，选择j段的最大的和。
代码：
#include <bits/stdc++.h>#include <functional>#include <algorithm>#include <iostream>#include <cstring>#include <cstdlib>#include <utility>#include <sstream>#include <complex>#include <cstdio>#include <bitset>#include <vector>#include <cmath>#include <queue>#include <stack>#include <ctime>#include <list>#include <set>#include <map>using namespace std;#define ll long long#define ull unsigned long longconst int MAXN=500005;const int INF=0x3f3f3f3f;const ll INFLL=9223372036854775807;const int MOD=1e9+7;int n, m, k;ll a[5005], sum[5005], dp[5005][5005];ll ans;int main(){//freopen("in.txt","r",stdin);//freopen("out.txt","w",stdout);cin>>n>>m>>k;for(int i=1; i<=n; i++){cin>>a[i];sum[i]=sum[i-1]+a[i];}for(int i=m; i<=n; i++){for(int j=1; j<=k; j++)dp[i][j]=max(dp[i-1][j], dp[i-m][j-1]+sum[i]-sum[i-m]);ans=max(ans, dp[i][k]);}cout<<ans<<endl;return 0;}
M.Cheap Travel
题意：
要坐n次地铁，有单程票，票价为a，有能用m次的通票，票价为b。给你n,m,a,b。求最少花多少钱。
思路：
考虑周全点，算一下呗。
代码：
#include <bits/stdc++.h>#include <functional>#include <algorithm>#include <iostream>#include <cstring>#include <cstdlib>#include <utility>#include <sstream>#include <complex>#include <cstdio>#include <bitset>#include <vector>#include <cmath>#include <queue>#include <stack>#include <ctime>#include <list>#include <set>#include <map>using namespace std;#define ll long long#define ull unsigned long longconst int MAXN=100005;const int INF=0x3f3f3f3f;const int MOD=1e9+7;int n, m, a, b;int main(){//freopen("in.txt","r",stdin);//freopen("out.txt","w",stdout);cin>>n>>m>>a>>b;if(m*a>b) cout<<min((n%m)*a+(n/m)*b, (n/m+1)*b)<<endl;else cout<<n*a<<endl;return 0;}
N.Wonder Room
题意：
n个人住房子，每个人需要面积为6，给你已有的边长为a和b的矩形房间，问你怎样扩建a和b，使面积能住下n个人且尽可能小。a,b均为正整数。
输出最小面积和此时a和b的值。
思路：
暴力枚举，跑到(6n)^0.5即可。
代码：
#include <bits/stdc++.h>#include <functional>#include <algorithm>#include <iostream>#include <cstring>#include <cstdlib>#include <utility>#include <sstream>#include <complex>#include <cstdio>#include <bitset>#include <vector>#include <cmath>#include <queue>#include <stack>#include <ctime>#include <list>#include <set>#include <map>using namespace std;#define ll long long#define ull unsigned long longconst int MAXN=100005;const int INF=0x3f3f3f3f;const int MOD=1e9+7;ll n, a, b, s, lim, ms, ma, mb;bool flag;int main(){//freopen("in.txt","r",stdin);//freopen("out.txt","w",stdout);ms=9223372036854775807;cin>>n>>a>>b;n*=6;if(a*b>=n){cout<<a*b<<endl;cout<<a<<' '<<b<<endl;return 0;}lim=(ll)(sqrt(n)+1);if(a>b){flag=true;swap(a, b);}for(ll i=a; i<lim; i++){s=n/i;if(n%i) s++;if(s<b) break;s*=i;if(s<ms){ms=s;ma=i;mb=s/i;}}if(flag) swap(ma, mb);cout<<ms<<endl;cout<<ma<<' '<<mb<<endl;return 0;}
O.Number of Ways
题意：
给出一个n长度序列，问多少种方法使得这个n长度序列分成3份，每一份值都相同
思路：
遍历一遍，找1/3处和2/3处，找到1/3处就cnt1++，找到2/3处就cnt2++。最后cnt2就是答案。
代码：
#include <bits/stdc++.h>#include <functional>#include <algorithm>#include <iostream>#include <cstring>#include <cstdlib>#include <utility>#include <sstream>#include <complex>#include <cstdio>#include <bitset>#include <vector>#include <cmath>#include <queue>#include <stack>#include <ctime>#include <list>#include <set>#include <map>using namespace std;#define ll long long#define ull unsigned long longconst int MAXN=500005;const int INF=0x3f3f3f3f;const ll INFLL=9223372036854775807;const int MOD=1e9+7;ll arr[MAXN], sum;ll n, t, cnt1, cnt2;int main(){//freopen("in.txt","r",stdin);//freopen("out.txt","w",stdout);cin>>n;for(int i=0; i<n; i++){cin>>t;sum+=t;arr[i]=sum;}if(arr[0]*3==sum) cnt1++;n--;for(int i=1; i<n; i++){if(arr[i]*3==2*sum) cnt2+=cnt1;if(arr[i]*3==sum) cnt1++;}cout<<cnt2<<endl;return 0;}