Dashboard - Educational Codeforces Round 138 (Rated for Div. 2) - Codeforces
总结一个教训就是不要心急,特别是对于一些题目,发现越写越复杂的时候,一定及时转换思路
Problem - A - Codeforces
有意思的一道题,由于必须移动,那么枚举移动位置,移动位置必须空白,条件是,同行同列没有冲突或者仅有一个冲突(把该冲突点放在这个移动位置)
#include <bits/stdc++.h>
using namespace std;typedef long long int ll;int a[100][100], x[100],y[100];
int main ()
{int t;cin>>t;while(t--){int n,m;cin>>n>>m;for(int i=1;i<=n;i++){for(int j=1;j<=m;j++){a[i][j]=0;}}for(int i=1;i<=m;i++){cin>>x[i]>>y[i];a[x[i]][y[i]]=1;}int flag=0;for(int i=1;i<=n;i++){for(int j=1;j<=m;j++){if(a[i][j]==0){int cnt=0;for(int ii=1;ii<=n;ii++){if(a[ii][j])cnt++;}for(int jj=1;jj<=m;jj++){if(a[i][jj])cnt++;}if(cnt<=1){flag=1;break;}}}}if(flag){cout<<"YES"<<endl;}else{cout<<"NO"<<endl;}}return 0;
}
Problem - B - Codeforces
B题真的是抽风了,本以为没开LL,开完又WA,白WA两次。实际上是贪心策略跑偏了。应该仔细研究模型,可见从一边开始进行消灭能使代价最小。这样每个人只能影响一次。减去最大值就行
#include <bits/stdc++.h>
using namespace std;typedef long long int ll;int main ()
{int t;cin>>t;while(t--){int n;cin>>n;ll ans=0,x,y;for(int i=1; i<=n; i++){cin>>x;ans+=x;}ll maxx=0;for(int i=1; i<=n; i++){cin>>y;ans+=y;maxx=max(maxx,y);}cout<<ans-maxx<<endl;}return 0;
}
Problem - C - Codeforces
C题算是一个小贪心与模拟
A同学想赢就应该保证每次都有删的数,而我们已知,每次删的数是必须减少的。那么就容易推知,每次都删最大的。
B同学为了让自己赢,就必须让A同学能删的越来越少,也就是把当前最小的给“破坏掉”
这样来看,n很小,k超过n的时候易知没有意义。故我们倒叙暴力枚举k,第一个答案就是我们要的。
#include <bits/stdc++.h>
using namespace std;typedef long long int ll;int a[110],n;
int temp[110];
bool check(int k)
{if(!k)return 1;for(int i=1; i<=n; i++){temp[i]=a[i];}int now=1;while(now<=k){int flag=0;int pos=0,maxx=0;for(int i=1; i<=n; i++){if(temp[i]==-1)continue;if(temp[i]<=k-now+1&&maxx<temp[i]){pos=i;maxx=temp[i];flag=1;}}if(flag==0){return 0;}temp[pos]=-1;pos=0;int minn=1e9;for(int i=1; i<=n; i++){if(temp[i]==-1)continue;if(temp[i]<minn){minn=temp[i];pos=i;}}temp[pos]+=k-now+1;now++;}return 1;}
int main ()
{int t;cin>>t;while(t--){cin>>n;for(int i=1; i<=n; i++){cin>>a[i];}for(int k=100; k>=0; k--){if(check(k)){cout<<k<<endl;break;}}}return 0;
}
Problem - D - Codeforces
D的突破点在于他给定的数列定义,要求拥有两个所谓的“序列”。前面很多话都是把人绕远的,实际上突破点就在这个不起眼的地方。拥有大于等于两个所谓的序列是合法的,言外之意就是一个是不合法的。有可能是0个吗,不可能,从头一直删一定可以。
这样就暗示我们,我们要排除的序列一定是只能从头往后删的,也就是说,我们位置i上面的数字,无论前面怎么缩短,始终找不到一个能使之gcd为1的位置(该位置小于等于i,通过消灭开头得到),既然如此,我们这样想,这个数字与前面的合数gcd不是1,与前面的质数gcd也不是1,特鄙视与质数gcd也不是1,那么其必定是前面所有质数的最小公倍数的若干倍,也就是前面所有质数的乘积!!那么前面的合数呢?合数就是两个质数的积!!,质数满足合数一定满足!
所以我们只需要预处理出n范围内全部质数,求出质数前缀积,每个位置也就有了方案数,乘法原理搞一搞,排斥一下即可
代码请在CF C++20版本下提交
#include <bits/stdc++.h>
# define mod 998244353
using namespace std;typedef __int128 ll;ll n,m;
ll dp[300000+10];int prime[300000+10],not_prime[300000+10],len;void init()
{for(int i=2;i<=300000;i++){if(!not_prime[i]){len++;prime[len]=i;}for(int j=1;j<=len&&prime[j]*i<=300000;j++){not_prime[i*prime[j]]=1;if(i%prime[j]==0)break;}}
}
ll x[300000+10];__int128 read(){__int128 x=0,f=1;char ch=getchar();while(!isdigit(ch)&&ch!='-')ch=getchar();if(ch=='-')f=-1,ch=getchar();while(isdigit(ch))x=x*10+ch-'0',ch=getchar();return f*x;
}
void print(__int128 x){if(x<0)putchar('-'),x=-x;if(x>9)print(x/10);putchar(x%10+'0');
}
int main()
{n=read();m=read();init();ll sum=0,now=1;ll tempm=m%mod;for(int i=1;i<=n;i++){now=(now*m)%mod;now%=mod;sum=(sum+now)%mod;}x[0]=1;x[1]=1;for(int i=1;i<=n;i++){if(!not_prime[i]){x[i]=x[i-1]*i;}else{x[i]=x[i-1];}}ll temp=1;for(int i=1;i<=n;i++){dp[i]=m/x[i];temp*=dp[i];temp%=mod;sum=((sum-temp)%mod+mod)%mod;}print(sum);return 0;
}