Educational Codeforces Round 138 (Rated for Div. 2)-赛后总结

Dashboard - Educational Codeforces Round 138 (Rated for Div. 2) - Codeforces

总结一个教训就是不要心急，特别是对于一些题目，发现越写越复杂的时候，一定及时转换思路

Problem - A - Codeforces

有意思的一道题，由于必须移动，那么枚举移动位置，移动位置必须空白，条件是，同行同列没有冲突或者仅有一个冲突（把该冲突点放在这个移动位置）

#include 
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"<
        }
        else
        {
            cout<<"NO"<
 
        }
    }
 
    return 0;
}

Problem - B - Codeforces

B题真的是抽风了，本以为没开LL，开完又WA，白WA两次。实际上是贪心策略跑偏了。应该仔细研究模型，可见从一边开始进行消灭能使代价最小。这样每个人只能影响一次。减去最大值就行

#include 
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<
 
    }
 
    return 0;
}

Problem - C - Codeforces

C题算是一个小贪心与模拟

A同学想赢就应该保证每次都有删的数，而我们已知，每次删的数是必须减少的。那么就容易推知，每次都删最大的。

B同学为了让自己赢，就必须让A同学能删的越来越少，也就是把当前最小的给“破坏掉” 

这样来看，n很小，k超过n的时候易知没有意义。故我们倒叙暴力枚举k,第一个答案就是我们要的。

#include 
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
            {
 
               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=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<
                break;
            }
 
        }
 
    }
 
 
    return 0;
}

Problem - D - Codeforces

D的突破点在于他给定的数列定义，要求拥有两个所谓的“序列”。前面很多话都是把人绕远的，实际上突破点就在这个不起眼的地方。拥有大于等于两个所谓的序列是合法的，言外之意就是一个是不合法的。有可能是0个吗，不可能，从头一直删一定可以。

这样就暗示我们，我们要排除的序列一定是只能从头往后删的，也就是说，我们位置i上面的数字，无论前面怎么缩短，始终找不到一个能使之gcd为1的位置（该位置小于等于i,通过消灭开头得到），既然如此，我们这样想，这个数字与前面的合数gcd不是1，与前面的质数gcd也不是1，特鄙视与质数gcd也不是1，那么其必定是前面所有质数的最小公倍数的若干倍，也就是前面所有质数的乘积！！那么前面的合数呢？合数就是两个质数的积！！，质数满足合数一定满足！

所以我们只需要预处理出n范围内全部质数，求出质数前缀积，每个位置也就有了方案数，乘法原理搞一搞，排斥一下即可

代码请在CF  C++20版本下提交

#include 
# 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;
}