A.Calendar
题意:
每一年 12 个月, 每个月 30 天, 每星期只有 5 天, 问下一个日期是星期几.
题解:
直接忽略年和月, 算天数就可以得到答案.
- #include<bits/stdc++.h>
- using namespace std;
- typedef int ll;
- int T;
- int year,month,day;
- int year1,month1,day1;
- string s[6]={"Monday","Tuesday","Wednesday","Thursday","Friday"};
- unordered_map<string,int> pos;
- int main () {
- scanf("%d",&T);
- string ss;
- for (int i=0;i<5;i++)
- pos[s[i]]=i;
- while (T--) {
- scanf("%d%d%d",&year,&month,&day);
- cin>>ss;
- scanf("%d%d%d",&year1,&month1,&day1);
- int t1=day;
- int t2=day1;
- int tmp=pos[ss];
- if (t1<=t2)
- tmp=(tmp+(t2-t1)%5)%5;
- else
- tmp=(tmp+5-(t1-t2)%5)%5;
- printf("%s\n",s[tmp].c_str());
- }
- return 0;
- }
- View Code
- B.Flipping Game
题意:
给你一串灯泡的初始状态和最终状态, 然后你可以进行 K 次操作, 每次操作可以选择任意 M 个灯泡来改变他们的状态, 询问你在 K 次操作后有多少种方案可以把灯泡从初始状态变成最终状态.
题解:
动态规划.
先预处理计算好范围内所有组合数的值, 然开一个二维 DP 数组, 表示第 i 步操作后有 j 个不同的状态, k 表示第 i+1 次操作后有 k 个不同的状态会被修正, 推出状态转移方程:
dp[i+1][j][j-k+M-k]+=dp[i][j]*c[j][k]*c[N-j][M-k]
- #include<bits/stdc++.h>
- using namespace std;
- const int maxn=105;
- const int mod=998244353;
- typedef long long ll;
- ll dp[maxn][maxn];
- ll c[maxn][maxn];
- // 表示第 i 步有 j 个不同的状态的方案数
- string s,t;
- int main () {
- int T;
- scanf("%d",&T);
- for (int i=0;i<maxn;i++)
- c[i][0]=1;
- for (int i=1;i<maxn;i++)
- c[i][i]=1;
- for (int i=2;i<maxn;i++)
- for (int j=1;j<i;j++)
- c[i][j]=(c[i-1][j-1]+c[i-1][j])%mod;
- while (T--) {
- int N,M,K;
- scanf("%d%d%d",&N,&K,&M);
- cin>>s>>t;
- int ans=0;
- for (int i=0;i<s.length();i++)
- ans+=s[i]!=t[i];
- memset(dp,0,sizeof(dp));
- dp[0][ans]=1;
- for (int i=0;i<=K;i++)
- for (int j=0;j<=N;j++)
- for (int k=0;k<=M;k++)
- if (k<=j) {
- dp[i+1][j-k+M-k]+=dp[i][j]*c[j][k]%mod*c[N-j][M-k]%mod;
- dp[i+1][j-k+M-k]%=mod;
- }
- printf("%lld\n",dp[K][0]);
- }
- return 0;
- }
- View Code
- C.Wandering Robot
题意:
给你一组机器人的指令, 并执行 K 次, 询问机器人在执行指令的过程中所能抵达的最远曼哈顿距离.
题解:
考虑两种情况:
机器人在第一组指令就达到了最远距离
机器人在第 K-1 组指令后达到了最远距离
以此进行模拟即可.
- #include<bits/stdc++.h>
- using namespace std;
- const int maxn=105;
- typedef long long ll;
- string s;
- int T;
- int N,K;
- ll x,y;
- int main () {
- scanf("%d",&T);
- while (T--) {
- scanf("%d %d",&N,&K);
- cin>>s;
- x=0;
- y=0;
- ll Max=-1;
- for (int i=0;i<N;i++) {
- if (s[i]=='U') y++;
- if (s[i]=='D') y--;
- if (s[i]=='L') x--;
- if (s[i]=='R') x++;
- Max=max(Max,abs(x)+abs(y));
- }
- x*=K-1;
- y*=K-1;
- for (int i=0;i<N;i++) {
- if (s[i]=='U') y++;
- if (s[i]=='D') y--;
- if (s[i]=='L') x--;
- if (s[i]=='R') x++;
- Max=max(Max,abs(x)+abs(y));
- }
- printf("%lld\n",Max);
- }
- return 0;
- }
- View Code
- D.Game On a Graph
题意:
有两个队的人, 他们轮流对一个图进行删边, 可以选择自己想删的边. 当删完边后这个图变得不再连通了, 就会输掉比赛.
给出图的信息, 询问哪个队会赢下比赛.
题解:
不断进行最优选择的情况下, 必定是当图只剩下 N-1 条边的时候删边的队伍输掉比赛, 找到那个编号的人所在的队伍, 输出另一个队即可.
- #include<bits/stdc++.h>
- using namespace std;
- const int maxn=1e6+14;
- string s;
- int N,M;
- int main () {
- int T;
- scanf("%d",&T);
- while (T--) {
- int len;
- scanf("%d",&len);
- cin>>s;
- scanf("%d%d",&N,&M);
- int x,y;
- for (int i=0;i<M;i++) scanf("%d%d",&x,&y);
- int tmp=(M-N+1)%len;
- if (s[tmp]=='1') printf("2\n");
- else printf("1\n");
- }
- return 0;
- }
- View Code
- E.BaoBao Loves Reading
题意:
书桌上有一些书, 给出一个书籍编号序列, 代表要读书的顺序, 当前要读的书在桌子上时就直接读, 不再桌子上时就去书架上拿, 书桌有一个容量, 当书桌满的时候需要把最早读的那本书放到书架上. 询问在书桌容量从 1 到 N 的时候各需要从书架上拿几次书.
题解:
推出两本相同的书之间有多少本不同的书, 这个数量如果大于 K(当前书桌容量) 就需要从书架上拿书.
考虑用线段树实现这个过程, 开一个前驱数组, 记录下每本书上次出现的位置, 每次统计数量的时候先把它上次的贡献剪掉, 再更新数量.'
- #include<bits/stdc++.h>
- using namespace std;
- const int maxn=1e5+10;
- int a[maxn];
- int b[maxn];
- int pre[maxn];
- int T;
- int N;
- struct node {
- int l;
- int r;
- int sum;
- }segTree[maxn*40];
- void build (int i,int l,int r) {
- segTree[i].sum=0;
- segTree[i].l=l;
- segTree[i].r=r;
- if (l==r) return;
- int mid=(l+r)>>1;
- build(i<<1,l,mid);
- build(i<<1|1,mid+1,r);
- }
- void update (int i,int t,int b) {
- if (segTree[i].l==t&&segTree[i].r==t) {
- segTree[i].sum+=b;
- return;
- }
- int mid=(segTree[i].l+segTree[i].r)>>1;
- if (t<=mid) update(i<<1,t,b);
- else update(i<<1|1,t,b);
- segTree[i].sum=segTree[i<<1].sum+segTree[i<<1|1].sum;
- }
- int query (int i,int l,int r) {
- if (segTree[i].l==l&&segTree[i].r==r) {
- return segTree[i].sum;
- }
- int mid=(segTree[i].l+segTree[i].r)>>1;
- if (r<=mid)
- return query(i<<1,l,r);
- if (l>mid)
- return query(i<<1|1,l,r);
- return query(i<<1,l,mid)+query(i<<1|1,mid+1,r);
- }
- int main () {
- scanf("%d",&T);
- while (T--) {
- scanf("%d",&N);
- memset(pre,0,sizeof(pre));
- memset(b,0,sizeof(b));
- build(1,1,N*4);
- for (int i=1;i<=N;i++)
- scanf("%d",&a[i]);
- for (int i=1;i<=N;i++) {
- if (!pre[a[i]]) {
- update(1,i,1);
- pre[a[i]]=i;
- continue;
- }
- update(1,pre[a[i]],-1);
- update(1,i,1);
- b[query(1,pre[a[i]],i)]++;
- pre[a[i]]=i;
- }
- for (int i=1;i<=N;i++) {
- if (i!=1) printf(" ");
- b[i]+=b[i-1];
- printf("%d",N-b[i]);
- }
- printf("\n");
- }
- return 0;
- }
- View Code
- L.Median
题意:
给出一组序列的大小以及里面的数的一些大小关系, 询问哪些数有可能成为中位数.
题解:
根据这些大小关系建立一个有向图, 跑一遍 floyd 算法.
当以下情况出现时, 这个序列是不合法的:
出现自环, 即 A 比 A 大
出现双向边, 即 A 比 B 大的同时 B 比 A 大
合法序列的前提下, 统计每个数一定比自己大的数的数目和一定比自己小的数的数目, 如果都小于 N/2, 那么这个数可以作为中位数.
- #include<bits/stdc++.h>
- using namespace std;
- const int maxn=105;
- const int inf=1e9;
- int T;
- int N,M;
- int g[maxn][maxn];
- int a[maxn];
- int l[maxn];
- int r[maxn];
- void floyd () {
- for (int k=1;k<=N;k++) {
- for (int i=1;i<=N;i++) {
- for (int j=1;j<=N;j++)
- g[i][j]=min(g[i][j],g[i][k]+g[k][j]);
- }
- }
- }
- int main () {
- int T;
- scanf("%d",&T);
- while (T--) {
- scanf("%d%d",&N,&M);
- memset(a,0,sizeof(a));
- memset(l,0,sizeof(l));
- memset(r,0,sizeof(r));
- for (int i=1;i<=N;i++)
- for (int j=1;j<=N;j++)
- g[i][j]=inf;
- for (int i=0;i<M;i++) {
- int x,y;
- scanf("%d%d",&x,&y);
- g[x][y]=1;
- }
- int flag=0;
- floyd();
- for (int i=1;i<=N;i++)
- for (int j=1;j<=N;j++)
- if (g[i][j]!=inf&&g[j][i]!=inf)
- flag=1;
- if (flag) {
- for (int i=0;i<N;i++)
- printf("0");
- printf("\n");
- continue;
- }
- for (int i=1;i<=N;i++) {
- for (int j=1;j<=N;j++) {
- if (g[i][j]!=inf) l[i]++,r[j]++;
- }
- }
- for (int i=1;i<=N;i++) {
- if (l[i]<=N/2&&r[i]<=N/2) a[i]=1;
- }
- for (int i=1;i<=N;i++) printf("%d",a[i]);
- printf("\n");
- }
- return 0;
- }
- View Code
来源: http://www.bubuko.com/infodetail-3461494.html