新生赛 10
今天没有学什么算法,主要是做了做往年的新生赛,虽然说估计应该最高只有一两个绿题的水平,基本上是黄题,但我的水平可以保证不能稳切绿题,黄题十有八九吃罚时。: (
A
贪心,一开始还煞有介事地开了个优先队列,给数组排了个序。
事实上优先队列等于没用,数组顺序不能更改,稳稳吃到 +2
#include<bits/stdc++.h>
#define int long long
using namespace std;
template<typename T>inline void re(T &x)
{x=0;int f=1;char c=getchar();while(!isdigit(c)){if(c=='-')f=-1;c=getchar();}while(isdigit(c)){x=(x<<1)+(x<<3)+(c^48);c=getchar();}x*=f;
}
template<typename T>inline void wr(T x)
{if(x<0)putchar('-'),x=-x;if(x>9)wr(x/10);putchar(x%10^48);
}
int a[1000000];
int n;
signed main()
{re(n);for(int i=2;i<=n;++i)re(a[i]);int ans=0;for(register int i=2;i<=n;++i)ans+=a[i]*i;wr(ans);return 0;
}
B
模拟题。类似记忆化,还好 1Y 了。
#include<bits/stdc++.h>
#define int long long
using namespace std;
int n,m,x,y,d;
const int N=600;
char mp[N][N];
bool vis[N][N][4];
int cx[4]={-1,0,1,0},cy[4]={0,1,0,-1};
inline int getd(int nowd,int x,int y)
{if(mp[x][y]=='.')return nowd;else if(mp[x][y]=='/'){switch(nowd){case 0:return 1;case 1:return 0;case 2:return 3;case 3:return 2;}}else // '\'{switch(nowd){case 0:return 3;case 1:return 2;case 2:return 1;case 3:return 0;}}
}
inline int dfs(int x,int y,int d,int s)
{if(vis[x][y][d])return -1;if(x>n||x<1||y<1||y>m)return s;vis[x][y][d]=1;int tx=x+cx[d],ty=y+cy[d];return dfs(tx,ty,getd(d,tx,ty),s+1);
}
inline void solve()
{cin>>n>>m>>x>>y>>d;for(int i=1;i<=n;++i){getchar();for(int j=1;j<=m;++j)mp[i][j]=getchar();}int ans=dfs(x,y,d,0);if(ans==-1)printf("Forever!");else cout<<ans;
}
signed main()
{solve();return 0;
}
C
人类智慧构造题,但好像还是挺好构造的,只不过我想了大概四十分钟才做出来,还是太废物了。
#include<bits/stdc++.h>
using namespace std;
template<typename T>inline void re(T &x)
{x=0;int f=1;char c=getchar();while(!isdigit(c)){if(c=='-')f=-1;c=getchar();}while(isdigit(c)){x=(x<<1)+(x<<3)+(c^48);c=getchar();}x*=f;
}
template<typename T>inline void wr(T x)
{if(x<0)putchar('-'),x=-x;if(x>9)wr(x/10);putchar(x%10^48);
}
int k;
int main()
{re(k);int p=0;for(int i=1;i<=k;++i){printf("%d %d %d\n",p,p+1,p+21);if(i%2)p+=22;else p+=41;}return 0;
}
D
感觉是一道大概有绿题思维难度的博弈,自己仅仅独立做出来了 \(\frac{1}{4}\) ,后面看着题解自己思考了一些。
题意
有一个 01 串,长度为 \(n\) ,如果一个 \(1\) 的右边是 \(0\) 的话,可以向右移动这个 \(1\) ,当一个 \(1\) 在串的最末尾的时候,可以移动它并且得到一分。
现在有 \(A,B\) 两个玩家,问如果他们都 optimally 地进行操作, 问最后谁的得分更高。
分析
首先来说,对于最右边的 \(1\) ,如果它距离串的末尾的距离是偶数,那么当前的人去移动它就肯定是一个必胜态;反之就是一个必败态,当前的人一定不会去移动它(除非没有其他的 \(1\) 可以移动)。
1.根据以上理论我们不难知道当一个串末尾为 \(0\) ,且有 \(2\) 个 \(1\) 的时候,一定会出现平局(无论谁先手),也可以推广偶数个 \(1\) 的情况。
2.当一个串末尾为 \(0\) 且有奇数个 \(1\) 的时候,考虑末尾的 \(1\) 出于必胜态还是必败态,如果是必胜态,那么当前的人一定会去移动它,将它变为必败态,这时候一定不会有人去移动它,而是去交替移动左边的 \(1\) ,直到达到 \(...111110\) 的情况为止,那么此时轮到谁先手操作需要由初始态到现在状态的操作数决定。容易思考出:此时先手的人必定会输。
3.当一个串末尾为 \(1\) 且有奇数个 \(1\) 的时候,先手必定赢,因为先手得分以后就是平局态。
4.当一个串末尾为 \(1\) 且有偶数个 \(1\) 的时候,先手先得一分,然后变成第二种情况。
Code
#include<bits/stdc++.h>
#define int long long
using namespace std;
template<typename T>inline void re(T &x)
{x=0;int f=1;char c=getchar();while(!isdigit(c)){if(c=='-')f=-1;c=getchar();}while(isdigit(c)){x=(x<<1)+(x<<3)+(c^48);c=getchar();}x*=f;
}
template<typename T>inline void wr(T x)
{if(x<0)putchar('-'),x=-x;if(x>9)wr(x/10);putchar(x%10^48);
}
int n;
signed main()
{re(n);char c[1000010];int cnt=0;for(int i=1;i<=n;++i){c[i]=getchar();if(c[i]=='1')cnt++;}int pos=n-1;for(;pos>=1;--pos)if(c[pos]=='1')break;if(c[n]=='0'){if(cnt%2==0)printf("Draw");else// {int s=0;for(int i=pos,idx=n;i;--i)if(c[i]=='1')s+=n-1-i-(n-idx),idx--;if(s%2)printf("Nigu");else printf("Frizea");}}else{if(cnt%2==1)printf("Nigu");else{int s=0;for(int i=pos,idx=n;i;--i)if(c[i]=='1')s+=n-1-i-(n-idx),idx--;if(s%2)printf("Draw");else printf("Nigu");}}return 0;
}
E
分析
这个是一眼不能贪心,所以就DP了。
图方便写了个记忆化,感觉复杂度应该挺小的,结果由于是第一次写浮点数的DP,咱判断记忆化的时候好像还不能直接用等于号,于是就 T 了两三发,索性写DP了,但是由于边界和层与层的嵌套关系没有搞得太清楚,调了很久,最后记忆化也改出来了,DP也写出来了。
细节
这个题的阶段是天数,非常明显了,然后应该从最后一天倒着枚举。
虽然看着是四层循环,但是实际上很小,可以通过。
Code
#include<bits/stdc++.h>
using namespace std;
int n;
double a[500][500],dp[500][500][10],sum[500][500];
inline void pre()
{cin>>n;int len=(int)pow(2,n);for(register int i=1;i<=len;++i)for(register int j=1;j<=len;++j)scanf("%lf",&a[i][j]); for(register int i=1;i<=len;++i)for(register int j=1;j<=len;++j)sum[i][j]=sum[i-1][j]+sum[i][j-1]+a[i][j]-sum[i-1][j-1];}
double calc(int i,int j,int x,int y)
{return sum[x][y]-sum[x][j-1]-sum[i-1][y]+sum[i-1][j-1];
}
inline double get(int x,int y,int k)
{if(k>n)return 0.0;if(dp[x][y][k]>0)return dp[x][y][k];//calcint l=(int)pow(2,n-k);double ans=0.0,div=pow(2,k);for(register int i=x;i<=x+l;++i)for(register int j=y;j<=y+l;++j)ans=max(ans,calc(i,j,i+l-1,j+l-1)/div+get(i,j,k+1)); return dp[x][y][k]=ans;
}
inline void memorized_search()
{int len=(int)pow(2,n);for(register int i=1;i<=len;++i)for(register int j=1;j<=len;++j)for(register int k=1;k<=n;++k)dp[i][j][k]=-1.0;printf("%.1lf",sum[len][len]-get(1,1,1));
}
inline void DP()
{int len=(int)pow(2,n);for(register int k=n;k>=1;--k){int l=(int)pow(2,n-k+1);for(register int i=1;i+l-1<=len;++i){for(register int j=1;j+l-1<=len;++j){for(register int u=i;u<=i+l/2;++u)for(register int v=j;v<=j+l/2;++v)dp[i][j][k]=max(dp[i][j][k],(dp[u][v][k+1]+calc(u,v,u+l/2-1,v+l/2-1))/2.0);}}}printf("%.1lf",sum[len][len]-dp[1][1][1]);
}
int main()
{pre();DP();
// memorized_search(); return 0;
}
F
人类智慧题,不多赘述,吃罚时就是了。
Code
#include<bits/stdc++.h>
#define int long long
using namespace std;
template<typename T>inline void re(T &x)
{x=0;int f=1;char c=getchar();while(!isdigit(c)){if(c=='-')f=-1;c=getchar();}while(isdigit(c)){x=(x<<1)+(x<<3)+(c^48);c=getchar();}x*=f;
}
template<typename T>inline void wr(T x)
{if(x<0)putchar('-'),x=-x;if(x>9)wr(x/10);putchar(x%10^48);
}
int T;
bool check(int a,int b,int c)
{int t=0; if(a==0)t++;if(c==0)t++;if(b==0)t++;return t<=1;
}
signed main()
{re(T);while(T--){int a,b,c;re(a),re(b),re(c);if(b==c)puts("Yes");else if(!check(a,b,c))puts("No");else{if(b>c)swap(b,c);if((c-b)%3!=0)puts("No");else puts("Yes");}}return 0;
}
G
模拟题 \(O(t\sqrt n)\) 可以通过
#include<bits/stdc++.h>
using namespace std;
inline void check(int x)
{int i;int ans=0;for(i=1;i*i<x;++i)if(x%i==0)ans+=2;if(i*i==x)ans++;if(x%ans==0)puts("YES");else puts("NO");
}
int main()
{int T;cin>>T;while(T--){int n;cin>>n;check(n);}return 0;}
H
模拟题
Code
#include<bits/stdc++.h>
using namespace std;
inline void solve(string s)
{cin>>s;int len=s.length();if(s[5]=='l'){for(register int i=9;i<=len-4;++i)putchar(s[i]);putchar('\n');}elsefor(register int i=7;i<=len-4;++i)putchar(s[i]);
}
int main()
{int L;cin>>L;L-=2;string s;cin>>s;while(L--)solve(s);cin>>s;return 0;
}
I
乍一眼看是个DP,结果发现好像不能重复,看了题解发现是个二分加贪心,写完了还是过不了,但倒是可以过样例,鸽了,不想改这题了。
Code
#include<bits/stdc++.h>
using namespace std;
char tmp[1000100],s[1000100];
int all_i,len;
inline void pre()
{cin>>s;len=strlen(s);for(register int i=0;i<len;++i)if(s[i]=='I')all_i++;
}
inline bool check(int x)
{int remain_I=0,remain_O=0,finished_I=0,find_I=0;for(register int i=len-1;i>=0;--i){if(s[i]=='I'){if(find_I!=x)find_I++,remain_I++;else if(remain_O)remain_I--,remain_O--,finished_I++;}if(s[i]=='O'&&remain_I!=0)remain_O++;if(s[i]=='N'&&remain_O!=0)remain_I--,remain_O--,finished_I++;}return finished_I==x;
}
inline int bs(int l,int r)
{if(l==r)return l;int mid=(l+r+1)>>1;if(check(mid))return bs(mid,r);else return bs(l,mid-1);
}
int main()
{pre();cout<<bs(0,len);return 0;
}
//IOIOIOIONIOIOI