今天第一场个人训练赛的题目有点恐怖啊，我看了半个小时多硬是一道都不会写。我干脆就直接补题去了。。。。
先补的都是简单题，难题等我这周末慢慢来吧。。。
A Calandar
http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemCode=4113
题目意思很明确：给出一个日期和对应的星期几，求出另一个所给的日期是星期几。
题目已经简化了，12个月，每月30天，一周5天，注意一下。
然而在补题的时候，我wa了好几发。。理了一下思路后，重写了以下a了。
虽说是签到题，但需要注意的有两点，一个是取模后需要注意为0的情况，一个是小于零的情况。
代码如下：
1 #include <iostream> 2 #include <bits/stdc++.h> 3 using namespace std; 4 typedef long long ll; 5 string Q[]={"0","Monday", "Tuesday", "Wednesday", "Thursday" ,"Friday"}; 6 int main() 7 { 8 int T; 9 cin>>T; 10 while(T--) 11 { 12 string s; 13 ll y1,m1,d1,y2,m2,d2,k; 14 cin>>y1>>m1>>d1>>s>>y2>>m2>>d2; 15 ll dt=(y2-y1)*360+(m2-m1)*30+d2-d1; 16 dt=dt%5; 17 if (dt<0) dt+=5; 18 for (int i=1; i<=5; i++) 19 { 20 if (Q[i]==s) 21 k=i; 22 } 23 k+=dt; 24 if (k%5==0) k=5; 25 else k=k%5; 26 cout<<Q[k]<<endl; 27 } 28 return 0; 29 }
C Wandering Robot
http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemCode=4115
题意：机器人从原点按指令走，整个过程距离原点最远距离是多少，距离定义为abs(x1-x2)+abs(y1-y2)
一开始考虑的是最远是在第k次，后来发现不对，例如下面这组样例：
7 2
UUUDDDD
所以比较一下第一次和第k次哪个远就好了，中间的次数按周期算，1和k模拟就好
代码如下：
#include <iostream> #include <bits/stdc++.h> using namespace std; typedef long long ll; int main() { int T; cin>>T; while (T--) { string s; ll n,k,x=0,y=0,ma1=-1,ma2=-1,ans; scanf("%lld%lld",&n,&k); cin>>s; s="0"+s; for (int i=1; i<=n; i++) { if (s[i]=='U') y++; else if (s[i]=='D') y--; else if (s[i]=='L') x--; else if (s[i]=='R') x++; ll cur=abs(x)+abs(y); if (cur>ma1) ma1=cur; } x*=k-1; y*=k-1; for (int i=1; i<=n; i++) { if (s[i]=='U') y++; else if (s[i]=='D') y--; else if (s[i]=='L') x--; else if (s[i]=='R') x++; ll cur=abs(x)+abs(y); if (cur>ma2) ma2=cur; } if (ma1>ma2) ans=ma1; else ans=ma2; printf("%lld ",ans); } return 0; }
http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemCode=4116
比赛的时候这道题我没看，队友敲的；
题意大概是说：有k个人玩游戏，分成1,2两组。游戏初始给出一个简单无向连通图，k个人周期依次操作，每次拿走一条边，仍然要保证图的联通，当取无边可取时（即目前状态取走任意一条边就会使图不再连通），该玩家所在的小组输掉游戏，游戏结束，输出赢家。
一开始觉得跟图的连通性有关，后来发现根本没有。保证n个点相连至少需要n-1条边，只需要求出可以去除几条边就完全可以了。同样注意取模后为0的情况，其他细节看代码吧。
代码如下：
#include <iostream> #include <bits/stdc++.h> using namespace std; typedef long long ll; const int maxn=1e5+10; char a[maxn]; int main() { int T; cin>>T; while (T--) { ll k,n,m; scanf("%lld",&k); scanf("%s",a+1); scanf("%lld%lld",&n,&m); for (int i=1; i<=m; i++) { int x,y; scanf("%d%d",&x,&y); } ll ov=m-n+1; ov%=k; if (a[ov+1]=='1') printf("2 "); else printf("1 "); } return 0; }
http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemCode=4118
这个题我敲了一半，然后队友接手直接过了，也不是很难；
题意：给你n堆石子，求出最少几次操作使得所有石子堆的石子个数相同。操作分两种：1。扔一个。 2。把一个石子从一堆移动到另一堆。
先判断需要扔的情况，注意扔的时候需要从最多的那一堆开始扔。
移动情况就是每堆与平均值的差了，记得除以2就行。
代码如下:
#include <iostream> #include <bits/stdc++.h> using namespace std; typedef long long ll; const int maxn=1e5+10; ll a[maxn]; bool cmp(ll x,ll y) { return x>y; } int main() { int T; cin>>T; while (T--) { ll n,sum=0,ave=0,ans=0; scanf("%lld",&n); for (int i=1; i<=n; i++) scanf("%lld",&a[i]),sum+=a[i]; ave=sum/n; ll ov=sum-ave*n,t; t=ov; sort(a+1,a+1+n,cmp); for (int i=1; i<=n; i++) { if (ov<=0) break; ll dt=a[i]-ave; if (ov>=dt) { ov-=dt; a[i]=ave; } else { a[i]-=ov; ov=0; break; } } for (int i=1; i<=n; i++) ans+=abs(a[i]-ave); ans/=2; ans+=t; printf("%lld ",ans); } return 0; }
题意很简单：死一次丢一半钱，n元钱，死k次，还剩多少？
注意特判。
代码如下：
#include <iostream> #include <bits/stdc++.h> using namespace std; typedef long long ll; int main() { int T; cin>>T; while (T--) { ll n,k; scanf("%lld %lld",&n,&k); if (k>32) k=32; while(k--) { if (n==1||n==0) break; if (n%2==0) n/=2; else n=n/2+1; } printf("%lld ",n); } return 0; }
http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemCode=4125
先写到这里吧。剩下的晚点补完！
5.17 补充 翻看ppt时，发现传递闭包那个题还可以bitset优化 改成 a[i][j]|=(a[i][k]&&a[k][j]);
优化后50ms-》30ms