考完试了,课设也基本上搞完了,终于可以一心补题了。
A:水题,宽和高任一是偶数就剪一刀,每减一次*2,第一刀从1->2,之后任一纸片都存在偶数个相同的,所以再剪一刀数量乘以2。
int main() { ios::sync_with_stdio; cin.tie(0); cout.tie(0); int t; cin >> t; while(t--) { int w,h,n; cin >> w >> h >> n; int cnt=1; while(w%2==0) { w/=2,cnt*=2; } while(h%2==0) { h/=2;cnt*=2; } if((cnt)>=n) cout << "YES" << endl; else cout << "NO" << endl; } return 0; }B:分糖果,糖果只重1或2,要求最后两人分得糖果能否等重。分类讨论,如果1的糖果为奇数个则不行。如果为偶数个(包括0),只有这种情况下不行——1的糖果数量为0且2的糖果数量不能均分,其他情况均能均分。
int main() { ios::sync_with_stdio; cin.tie(0); cout.tie(0); int t; cin >> t; while(t--){ int n; scanf("%d",&n); int cnt1=0,cnt2=0,x; for(int i=1;i<=n;i++){ scanf("%d",&x); if(x==1) cnt1++; else cnt2++; } if(cnt1%2==0){ if(cnt1==0&&cnt2%2!=0) puts("NO"); else puts("YES"); } else puts("NO"); } return 0; }
C:一数组a含有n个元素,给你一个任意一个起始点,当 i<=n时, i=i+a[i],得分score = score + a[i],当i>n结束移动,试求出对于数组a可以得出的最大得分。
思路:倒着模拟一遍,如果i+a[i]<=n,我们就加上它移动后所在的位置的分数,即a[i]+=a[i+a[i]],每次比较求最大值,最后输出即可,当模拟完求出来的ans就是从当前位置移动到 i>n结束时的最大值。
int main() { ios::sync_with_stdio; cin.tie(0); cout.tie(0); int t; cin >> t; while(t--){ int n; cin >> n; for(int i=1;i<=n;i++) cin >> a[i]; int ans=0; for(int i=n;i>0;i--) { if((i+a[i])<=n) a[i]+=a[i+a[i]]; ans=max(a[i],ans); } cout << ans << endl; } return 0; }D:简单博弈,Alice只有取偶数才加分,Bob只取奇数才加分。假设此时A与B相差x分且A先手,如果这个数为偶数,A取这个数y后那么他们的差值将变为x+y,如果时奇数不取的话就会被B取了,那他们的分数的差值就缩小了。对于B也一样。他们都采取最优策略,所以我们只要将所有数排序每个人从大到小取就行,如果遇到不能取的数(如当前A取可数是奇数,我们也取了,虽然不会加分,但可以避免缩小A与B分数之间的插值)
bool cmp(int x,int y) { return x>y; } int main() { ios::sync_with_stdio; cin.tie(0); cout.tie(0); int t; cin >> t; while(t--){ int n; cin >> n; //vector<int>v1,v2; for(int i=1;i<=n;i++) { cin >> a[i]; } sort(a+1,a+1+n,cmp); ll sum1=0,sum2=0; for(int i=1;i<=n;i++) { if(i%2) { if(a[i]%2==0) sum1+=a[i]; } else { if(a[i]%2) sum2+=a[i]; } } if(sum1>sum2) cout << "Alice" << endl; else if(sum1==sum2) cout << "Tie" << endl; else cout << "Bob" << endl; } return 0; }写到这发现课设报告还没写完。。。明天交了,先把报告整完明天再继续补。
E: n个人排队占位有严格的要求,当一个人A的身高比另外一个人B的身高矮,且宽度比他小时,A可以站在B的前面,或者当A身高比B宽度小时,且宽度比B身高小时,A可以躺在B前面。想知道每个人是否有对应的人可以站或躺在他的前面,如果有,则输出那个人的编号,若有多个,则输出任意一个,如果没有则输出-1。
思路:通过题意我们发现(h1,w1)和(h2,w2),只有当前面的二元组的最大值大于后面的二元组的最大值且前面的二元组的最小值大于后面的二元组的最小值才符合条件,即:max(h1,w1)>max(h2,w2)且min(h1,w1)>min(h2,w2)。那我们就对每一个二元组的最大值进行从小到大排序,循环遍历的时候,维护一个最小值(即每个二元组中较小的那个值)。每次循环都与最小值比较一次,不断更新即可。
#include <bits/stdc++.h> #define INF 0x3f3f3f3f using namespace std; const int N = 2e5+5; struct node{ int maxn,minn,pos;//二元组中的较大值、较小值、位置 }T[N]; int ans[N]; bool cmp(node x, node y) { return x.maxn<y.maxn; } int p; int main() { int t; cin >> t; while(t--) { int n; cin >> n; memset(ans,-1,sizeof(ans)); for(int i=1;i<=n;i++) { int h,w; cin >> h >> w; T[i].maxn=max(h,w); T[i].minn=min(h,w); T[i].pos=i;//每个人的位置 } sort(T+1,T+1+n,cmp);//按每个二元组中的较大值进行从小到大排序 int Min=INF; for(int i=1,t=i+1; i<=n; i=t) { while(T[i].maxn==T[t].maxn&&t<=n) t++;//如果最大值相同 不满足题意的严格小于这一条件 继续往后走 for(int j=i; j<=t-1; j++) { if(T[j].minn>Min)//说明有人可以排在他前面,记录下是第几个人 { ans[T[j].pos]=p; } } for(int j=i; j<=t-1; j++) { if(T[j].minn<Min)//更新最小值和位置 { Min=T[j].minn; p=T[j].pos; } } } for(int i=1;i<=n;i++) cout << ans[i] << " "; cout << endl; } return 0; }F:
题意:一个2*n的网格,其中某些点被涂黑,意味着这个点不能放东西,求剩下的格子能不能被1*2或2*1的瓷砖填满
思路:读完题我的思路就是只要考虑涂黑单元格之间即可,因为如果最左和最右两端的黑色单元格还有未填充的,那一定可以被上面两种瓷砖填满。然后我们来讨论,当有一列有一个被涂黑那接下来只能放1*2的瓷砖,直到碰见下一个黑格(这一列只有一个),且黑格的坐标(r,c)之和要与上一个黑格的坐标奇偶性相反才能在这两黑块之间用上面两种瓷砖填满(不明白的草稿纸上画一下就明白了),如果下一个黑块所在列均为黑块,那么填不满,因为黑块之间的空白格是奇数。每找到下一个黑块我们就判断与上一个黑块之间坐标和的奇偶性,如果相同说明不能填完,直接break跳出输出no,否则更新一下。
int main() { ios::sync_with_stdio; cin.tie(0); cout.tie(0); int t; cin >> t; while(t--) { cout << endl; int n,m; cin >> n >> m; map<int,int>mp;//用map来存黑格这一列的坐标和,1代表黑格在第一行,2代表在第2行,3代表都有 for(int i=1;i<=m;i++) { int r,c; cin >> r >> c; mp[c]+=r; } int flag=1,last=-1;//last为-1当前是从任意一端相邻黑块 for(auto i : mp) { if(last==-1)//这一段内第一块黑砖 { if(i.second!=3) last=i.first+i.second; //说明这一块黑格所在的列只有一块黑格 //因为如果这一列都为黑格对答案没有影响,我们可一直放1*2的瓷砖直到遇到下一个黑格 } else { if(i.second==3)//一列中全为黑色单元格 {//前面已经出现一个黑格了 又来两个 那他们之间的空白格就为奇数 不满足 flag=0; break; } if((last+i.first+i.second)%2==0) { //相邻两个黑块的坐标和奇偶相同 不满足 flag=0; break; } last=-1;//说明这两段黑块之间可以被填满,更新一下 } } if(last!=-1) flag=0; if(flag) cout << "YES" << endl; else cout << "NO" << endl; } return 0; }G:图。。。溜了溜了,但题意不难,读完感觉也不难,以后补
题意:
有一个由 n个结点组成的有向图。一些结点由边长为1的有向边相连。
已知一个数组 d1...n,其中di 为从编号为 1 的结点到编号为 ii的结点的最短距离。 你站在第 s 个节点上。你有以下几种选择:
- 沿着某条边,从第 i 个结点到第 j 个结点, di<dj;
- 沿着某条边,从第 i 个结点到第 j 个结点,di≥dj;(每局最多只能走一次)
输出n个数,代表第i个节点出发到第 1 个结点的最短距离。