NEFU 大一寒假2.22考试 2020.02.22

Summary

这次考试考的人都傻了，这让我充分的认识到了我是有多菜 /(ㄒoㄒ)\~~
也充分认识到了读题和解题顺序的重要性 /(ㄒoㄒ)\~~ x2
由于做题顺序不对导致会的题没看真的是太遗憾了 /(ㄒoㄒ)\~~ x3
（我不会告诉你我 EFG 三个题看都没来得及看）/(ㄒoㄒ)\~~

2020.02.23 休息一天（写个小软件，再调整一下家里的网络）
2020.02.24 疯狂补题+写这篇文章

Information

Problem A: 熊熊对对碰 (2122) [33/166]

Tips

A 这个题啊，理解了是真的一点都不难，代码也没几行，但是我这次考试却偏偏死在这A题了。大量的时间都去改这个 A 题，然后。。。

好吧，看看我是怎么折在这个要把我搞疯了的简单A题上的。
首先这个题目是这样说的：

我们对于每头熊的名字用两个数字x,y表示，如果坐标为(x,y)的熊与坐标为(-x,-y)的熊的总数为偶数，那么坐标为(x,y)和(-x,-y)的熊都会掐起来；如果和是奇数，为了不让别的熊看戏，他们就不会掐起来。

那既然 (x,y) 是熊的名字，直觉告诉我同名的熊应该不会打起来吧。
假设这样的测试数据：

2
1 1
1 1

就像这样：
– “你叫啥，我叫 (1,1)”
– “嘿，巧了兄弟，我也叫 (1,1)”
– “咱们看看对面 (-1,-1) 有没有熊，咱们干他去！”
– “对面好像没熊，咱兄弟俩唠唠嗑吧。”
– “好嘞！”
Output：0 Wrong Answer ❌

结果事实却恰恰相反，实际情况是这样的：
– “你叫啥，我叫 (1,1)”
– “嘿，你咋抢我名呢？我叫 (1,1)”
– “对面 (-1,-1) 没有熊，要不咱俩先干一架啊？”
– “好嘞！”
Output：2 Accepted ✔

What ？？？这都是啥情况 ？？？！！！
好吧 ╮(╯-╰)╭，回到正常模式。嗯，说到啥地方来着？
不要忘了 (0,0) 这个特殊情况，(0,0) 不要加成二倍就好。

Code

#include <bits/stdc++.h>
using namespace std;int main()
{map<pair<int,int>,int>m;int n,x,y,ans=0,sum,h;scanf("%d",&n);while(n--){scanf("%d %d",&x,&y);m[make_pair(x,y)]++;sum=m[make_pair(x,y)]+m[make_pair(-x,-y)];if(x==0&&y==0)sum/=2;if(sum%2==0)ans+=sum;else ans-=sum-1;}printf("%d",ans);return 0;
}

Problem B: 秘籍 (2120) [20/117]

Tips

可以从头开始确定一个区间，长度为 1（l=r=1），计算区间和（num[0]）
如果区间和大于 k，区间右边界向右移动，
如果区间和小于 k，区间左边界向右移动。注意此时如果左右边界重合需要继续向右移动右边界，直到右边界到头。
方法不难，这应该就是俗称的尺取法吧。

Code

#include <bits/stdc++.h>
using namespace std;long long num[300001],sum=0;
int main()
{int n,k,l,r;scanf("%d %d",&n,&k);for(int i=0;i<n;i++)scanf("%lld",&num[i]);l=r=0;sum=num[0];while(1){if(sum==k)break;else if(sum<k){if(r+1<n)sum+=num[++r];else break;}else{if(l+1<=r)sum-=num[l++];else if(r+1<n)sum+=num[++r];else break;}}if(sum==k)printf("%d %d",l+1,r+1);else printf("tiangeniupi");return 0;
}

Problem C: jwGG的签到题 (2103) [16/98]

Tips

这个 jwMMGG的签到题乍一看有点难度，仔细研究研究发现是个规律题。
观察一下测试数据的解释，自己再推一推就可以找到规律了：
根据这个进行处理 x*y=line(x,y)-x-y，先假设 xy 都是一位数，此时 line(x,y)=x*10+y
代入原式 x*y=x*10+y-x-y=x*9，约掉两侧的 x，得到 y=9
说明 符合条件的 y 是固定的，并且无论 x 取什么值，只要 y 满足条件就可以了。
再依次列举两位数、三位数的情况，发现 满足条件的 y 值为 9,99,999,9999…
所以求出 上限 b 中包含多少个 9,99,999,9999…，即 b+1 的位数。

Code

#include <bits/stdc++.h>
using namespace std;int main()
{unsigned long long a,b,ans;char tmp[20];int t;scanf("%d",&t);while(t--){scanf("%llu %llu",&a,&b);sprintf(tmp,"%llu",b+1);ans=(strlen(tmp)-1)*a;printf("%llu\n",ans);}return 0;
}

Problem D: jwMM的疯狂A-B (2133) [65/150]

Tips

利用 set 去重，模拟相减过程（比较元素）即可，不用真的减一下。

Code

#include <bits/stdc++.h>
using namespace std;int main()
{set<int>s1,s2;int tmp,ok=0,m,n;scanf("%d %d",&n,&m);for(int i=0;i<n;i++){scanf("%d",&tmp);s1.insert(tmp);}for(int i=0;i<m;i++){scanf("%d",&tmp);s2.insert(tmp);}for(set<int>::iterator it=s1.begin();it!=s1.end();it++){if(!s2.count(*it)){printf("%d\n",*it);ok=1;}}if(!ok)printf("So crazy!!!");return 0;
}

Problem E: 煊哥的难题 (2126) [2/26]

Tips

其实这题不算太难，考试没看这题，后悔 ing。
分别存一下斜率存在和不存在条件下平行，重合的情况。

Code

#include <bits/stdc++.h>
using namespace std;int main()
{map<pair<double,double>,int>m;//k b 记录y=kx+bmap<double,int>m2;//k 记录所有斜率为k的map<double,int>nk;//k不存在，存xdouble k,b;int n,x1,x2,y1,y2,kcnt=0,nkcnt=0;long long ans=0;scanf("%d",&n);while(n--){scanf("%d %d %d %d",&x1,&y1,&x2,&y2);if(x2-x1!=0) //斜率存在{k=(double)(y2-y1)/(x2-x1);b=y1-k*x1;ans+=kcnt+nkcnt-m2[k]+m[{k,b}];kcnt++;m[{k,b}]++;m2[k]++;}else //斜率不存在{ans+=kcnt+nk[x1];nk[x1]++;nkcnt++;}}printf("%lld",ans);return 0;
}

Problem F: jwGG与yzMM的字符串 (2106) [2/19]

Tips

考试也没看这题，扫了一眼感觉太长了，后悔 ing。
借鉴了大佬 jwMM 的打表法，要不然我就在里面暴力算了。
先算出所有的密码反查表，然后直接对应解密即可。
注意：解密顺序与加密顺序相反。

Code

#include <bits/stdc++.h>
using namespace std;int main()
{char str[1000][1001],pass[128][128],dict[52],tmp;pair<int,int>p[100000];int n,m,pp=0,x,y,lenx,leny;for(int i=0;i<=25;i++)dict[i]='A'+i;for(int i=26;i<=51;i++)dict[i]='a'-26+i;for(int i=0;i<=51;i++){for(int j=0;j<=51;j++){tmp=(i+j)%52;pass[dict[i]][dict[tmp]]=dict[j];}}scanf("%d %d",&n,&m);for(int i=0;i<m;i++){scanf("%d %d",&x,&y);p[pp].first=x;p[pp++].second=y;}for(int i=0;i<n;i++){scanf("%s",&str[i]);}for(int i=pp-1;i>=0;i--){x=p[i].first-1;y=p[i].second-1;lenx=strlen(str[x]);leny=strlen(str[y]);for(int j=0;j<leny;j++){str[y][j]=pass[str[x][j%lenx]][str[y][j]];}}for(int i=0;i<n;i++){printf("%s\n",str[i]);}return 0;
}

Problem G: jwGG与bwMM的字符串 (2107) [2/7]

Tips

考试也没看这题，这个也不短太长了，以为特别难，结果。。。
稍微有点麻烦的就是推一下规律。

首先这个空串做前缀只有 x=0 的时候才满足条件，这个还算好想。
剩下的我是第一遍循环计算答案的同时 记录距离满足要求的 01 差值，第二次循环的时候再计算一次，如果 两次之间的增量是第一次计算的整数倍，说明在 后面的一次循环里可以使这个位置上的字符满足要求，因此答案再 +1。

第一轮有字符满足条件，第二轮依然满足，说明后面无限循环，输出 -1。

Code

#include <bits/stdc++.h>
using namespace std;int main()
{int t,n,x,n0,n1,ans,offset[100001],newoffset,ok;char str[100001];scanf("%d",&t);while(t--){scanf("%d %d",&n,&x);scanf("%s",str);ans=n0=n1=0;ok=1;if(x==0)ans++;for(int i=0;i<n;i++){if(str[i]=='0')n0++;else n1++;if(n0-n1==x)ans++;offset[i]=n0-n1-x;}for(int i=0;i<n;i++){if(str[i]=='0')n0++;else n1++;newoffset=n0-n1-x;if(offset[i]!=0&&offset[i]-newoffset!=0&&abs(newoffset)<abs(offset[i])&&offset[i]%(offset[i]-newoffset)==0)ans++;if(offset[i]==0&&newoffset==0){ok=0;break;}}if(ok)printf("%d\n",ans);else printf("-1\n");}return 0;
}

Problem H: 库特放书 (2123) [3/38]

Tips

现在我一看到库特我就害怕，快整出来条件反射了。
我用二分写了将近一个小时就是过不去，结果这题不能用二分。
补题的时候删掉一大串二分代码时心都在滴血。。。

为什么这个不能二分呢？因为据说这个答案不具有单调性，好吧，还真是。
所以既然不能二分，那就暴力解决吧，反正数据范围 1000，应该还可以。
难得有一天暴力是 AC 之母，二分是 WA 之母。

发现大佬 jwMM 的思路不错，原来想的数组标记删除不太方便，并且可能耗时也不短，于是就按照 jwMM 的方法写了一下。
首先读入排序没什么难度，剩下的就是往一个桶里扔书，先挑大的扔，先大后小，都扔进去了即为成功，要是剩下书进不去（或者箱子太多）即为失败。
由于是 从小到大进行暴力 尝试的，所以第一个成功的一定是最小的。
其中 枚举下界为 sum/m 即将所有书的体积平均分配到 m 个箱子里。
最后不要忘了输出格式 Case #%d: %d

Code

#include <bits/stdc++.h>
using namespace std;int main()
{int t,n,m,v[1001],mv,l,sum,ok,pos,rest,cnt;scanf("%d",&t);for(int cas=1;cas<=t;cas++){mv=-1;sum=0;scanf("%d %d",&n,&m);for(int i=0;i<n;i++){scanf("%d",&v[i]);if(v[i]>mv)mv=v[i];sum+=v[i];}sort(v,v+n);l=sum/m;do{rest=l; //箱子剩余体积cnt=1; //已使用箱子数量vector<int>books(v,v+n);while(!books.empty()){pos=upper_bound(books.begin(),books.end(),rest)-books.begin()-1; //找最大能放下的书if(pos>=0) //放进去{rest-=books[pos];books.erase(books.begin()+pos);}else //放不下{cnt++; //one more boxrest=l;if(cnt>m)break; //箱子过多失败跳出}}if(cnt<=m)break; //找到答案跳出}while(l++); //不停递增printf("Case #%d: %d\n",cas,l);}return 0;
}