Educational Codeforces Round 83 (Rated for Div. 2) A~~E

A 水题

代码语言：javascript复制

#include<bits/stdc  .h>

using namespace std;

int main(){
	int t;
	cin>>t;
	while(t--){
	int n,m;
	cin>>n>>m;
	if(n % m==0) cout<<"YES"<<endl;
	else cout<<"NO"<<endl;	
	}
}

B 水题

代码语言：javascript复制

#include<bits/stdc  .h>

using namespace std;

int a[105];

int main(){
	int t;
	cin>>t;
	while(t--){
		int n;
		cin>>n;
		for(int i=0;i<n;i  ){
			cin>>a[i];
		}
		sort(a,a n);
		for(int i=n-1;i>=1;i--) cout<<a[i]<<" ";
		cout<<a[0]<<endl; 
	}
	return 0;
}

C水题

代码语言：javascript复制

#include<bits/stdc  .h>
using namespace std;
typedef long long LL;

int T;
int n,k;
int a[70];
LL a;

int main()
{
    cin>>T;
    while(T--)
    {
        memset(a,0,sizeof(a))
        cin>>n>>k;
        bool flag=0;
        for(int i=0;i<n;i  )
        {
            cin>>a;
            LL tmp=a;
            int j=0;
            while(tmp)
            {
                a[j] =(tmp%k);
                if(a[j]>1){flag=1;break;}
                j  ;
                tmp=tmp/k;
            }   
        }
        if(!flag)puts("YES");
        else puts("NO");
        
    }
    return 0;
}

D. 组合问题

代码语言：javascript复制

#include<bits/stdc  .h>
using namespace std;
#define ll long long
#define mod 998244353
const ll maxn=2e5 10;
ll n,m,t;
ll ksm(ll a,ll b)
{
    if(b<0)
        return 0;
    ll ans=1;
    while(b)
    {
        if(b&1)
            ans=ans*a%mod;
        a=a*a%mod;
        b>>=1;
    }
    return ans;
}
ll exgcd(ll a,ll b,ll &x,ll &y){
    if(!b){
        x=1;y=0;
        return a;
    }
    ll d=exgcd(b,a%b,x,y);
    ll tmp=x;
    x=y;
    y=tmp-a/b*y;
    return d;
}
ll inv(ll a,ll m){
    ll x,y;
    ll d=exgcd(a,m,x,y);
    if(d==1){
        return (x%m m)%m;
    }
    return -1;
}
int main(){
    cin>>n>>m;
    ll nn=n-1;
    ll sum=0;
    ll a=1,b=1;int f=1;
    for(ll i=m;i>=m-nn 1 ;i--){
        a*=i;a%=mod;
        b*=(m-i 1);b%=mod;
    }
    sum=a*inv(b,mod)%mod;

    ll k=(n-2)*ksm(2,n-3)%mod;
    sum*=k;
    sum%=mod;
    cout<<sum<<endl;
    return 0;
}

E 大佬题解表示不会，dp没想到

代码语言：javascript复制

#include<bits/stdc  .h>
using namespace std;
#define mem(a,b) memset(a,b,sizeof(a))
typedef long long LL;
 
inline int read()
{
    int x=0,f=1;char c=getchar();
    while(!isdigit(c)){if(c=='-')f=-1;c=getchar();}
    while(isdigit(c)){x=x*10 c-'0';c=getchar();}
    return x*f;
}
const int maxn=510;
int n,a[maxn],dp[maxn][maxn],vis[maxn][maxn],f[maxn];
int DP(int L,int R)
{
    if(vis[L][R])return dp[L][R];
    vis[L][R]=1;
    int &res=dp[L][R];
    if(R<L)return -1;
    if(R==L)return res=a[L];
    for(int i=L;i<R;i  )
        if(DP(L,i)==DP(i 1,R) && DP(L,i)!=-1)return res=DP(L,i) 1;
    return res;
}
int main()
{
    mem(dp,-1);
    n=read();
    for(int i=1;i<=n;i  )a[i]=read();
    DP(1,n);
    mem(f,42);
    f[0]=0;
    for(int i=1;i<=n;i  )
        for(int j=1;j<=i;j  )
            if(dp[j][i]!=-1)f[i]=min(f[i],f[j-1] 1);
    printf("%dn",f[n]);
    return 0;
}

0 人点赞