CodeforcesRound#493(Div.2)解(bu)题记录

#include
using namespace std;
int a[1100];int n;
int main(){
    scanf("%d",&n);int sum=0;
    for(int i=1;i<=n;i++) scanf("%d",&a[i]),sum+=a[i];
    if(n<=1){puts("-1");return 0;}
    if(n==2&&a[1]==a[2]) {puts("-1");return 0;}
    for(int i=1;i<=n;i++){
        if(a[i]!=sum-a[i]){
            puts("1");
            printf("%d\n",i);
            return 0;
        }
    }    
    
    return 0;
}

#include
using namespace std;
int a[110],sum[110][2];
//0 odd
multiset<int>se;
int main(){
    int n,b,num1=0,num2=0,ans=0,sum=0;
    scanf("%d%d",&n,&b);a[n+1]=1e9;
    for(int i=1;i<=n;i++) scanf("%d",&a[i]);
    for(int i=1;i<=n;i++){
        if(a[i]&1) num1++;
        else num2++;
        if(num1==num2) {
            ans++;
            int tmp=abs(a[i+1]-a[i]);
            se.insert(tmp);sum+=tmp;
        }
    }
    while(sum>b){
        ans--;sum-=*se.rbegin();
        auto it=se.end();it--;
        se.erase(it);
    }
    printf("%d\n",ans);
    return 0;
}

#include
using namespace std;
const int N=3e5+10;
typedef long long ll;
char s[N],s_[N];
int main(){
    int n,x,y;
    scanf("%d%d%d",&n,&x,&y);getchar();
    scanf("%s",s+1);int cnt=0;
    for(int i=1;i<=n;i++){
        s_[++cnt]=s[i];
        while(s[i+1]==s[i]) i++;
    }
    int num=0,num0=0;
    for(int i=1;i<=cnt;i++) if(s_[i]=='0') num0++;
    ll ans=1e18;
    for(ll i=0;i<=num0-1;i++){
        ll tmp=num0-i;
        ans=min(ans,tmp*y+i*x);
    }
    if(ans==1e18) ans=0;
    printf("%I64d\n",ans);
    return 0;
}

#include
using namespace std;
set<int>se;
int a[4]={1,5,10,50};
void dfs(int n,int now){
    if(n==0) {se.insert(now);return;}
    for(int i=0;i<4;i++){
        dfs(n-1,now+a[i]);
    }
}
int f[13]={0,4,10,20,35,56,83,116,155,198,244,292,341};
int main(){
    int n;
    while(cin>>n){
        if(n<=12) cout<endl;
        else{
            long long ans=1ll*49*(n-12)+f[12];
            cout<endl;
        }
    }
    return 0;
}

#include
using namespace std;
const int N=1e6+10;
typedef long long ll;
const ll mod=998244353;
ll fac[N],inv_fac[N];
ll qpow(ll a,ll b){
    ll res=1,tmp=a;
    for(;b;b>>=1,(tmp*=tmp)%=mod) 
        if(b&1) (res*=tmp)%=mod;
    return res;
}
void init(){
    fac[0]=1;
    for(int i=1;i1]*i%mod;
    inv_fac[N-1]=qpow(fac[N-1],mod-2);
    for(int i=N-2;i>=0;i--) inv_fac[i]=inv_fac[i+1]*(i+1)%mod; 
}
ll C(int n,int m){
    return (fac[n]*inv_fac[n-m]%mod)*inv_fac[m]%mod;
}
ll add(ll a,ll b) {
    a=(a+b)%mod;
    if(a<0) return a+mod;
    return a;
}
int main(){
    int n;scanf("%d",&n);init();ll ans=0;
    if(n==1){printf("3\n");return 0;}
    int s=1;
    ll pow3=1;
    ll p3n = qpow(3, n);
    for(ll i=1;i<=n;i++,s*=-1){
        ll tmp=s*C(n,i)*qpow(3,i)%mod*qpow(3,n*(n-i)%(mod-1))%mod;
        ans=add(ans,tmp); 
    }
    ans=add(ans,ans); 
    s=(n&1)?1:-1;
    for(ll i=0;i1){
        ll tmp=add(qpow(qpow(3,i)-1,n),-qpow(3,1ll*n*i%(mod-1)));
        (tmp*=3*s*C(n,i))%=mod;
        ans=add(ans,tmp);
    }
    printf("%I64d\n",ans);
    return 0;
}