AtCoder Beginner Contest 159

AtCoder Beginner Contest 159

A.The Number of Even Pairs

a,b=map(int,input().split())
print(a*(a-1)//2+b*(b-1)//2)

B.String Palindrome

bool is(string s){
    string t=s;
    reverse(t.begin(),t.end());
    return s==t;
}
int main(){
    string s;
    cin>>s;
    int n=s.size();
    if(is(s)){
        if(is(s.substr(0,(n-1)/2))){
            if(is(s.substr((n+3)/2-1))){
                O("Yes");
            }else O("No");
        }else O("No");
    }else O("No");
}

C.Maximum Volume

L=int(input())
print((L/3)**3)

D.Banned K

int n;
int a[N];
ll b[N];
int main(){
    //IN
    cin>>n;
    ll ans=0;
    for(int i=0;i++<n;sc("%d",&a[i]),b[a[i]]++);
    for(int i=1;i<=n;i++){
        ans+=b[i]*(b[i]-1)/2;
    }
    for(int i=1;i<=n;i++){
        pr("%lld\n",ans-(b[a[i]]-1));
    }
}

E.Dividing Chocolate

二进制枚举行的状态。

#include<bits/stdc++.h>
using namespace std;
#define me(a,x) memset(a,x,sizeof(a))
#define sc scanf
#define pr printf
#define IN freopen("in.txt","r",stdin);
#define OUT freopen("out.txt","w",stdout);
typedef long long ll;
typedef unsigned long long ull;
const int N=1e6+6;
const int mod=1e9+7;
template<typename T>int O(T s){cout<<s<<endl;return 0;}
template<typename T>void db(T *bg,T *ed){while(bg!=ed)cout<<*bg++<<' ';pr("\n");}
template<typename T>void db(vector<T>it){for(auto i:it)cout<<i<<' ';pr("\n");}
inline ll mul_64(ll x,ll y,ll c){return (x*y-(ll)((long double)x/c*y)*c+c)%c;}
inline ll ksm(ll a,ll b,ll c){ll ans=1;for(;b;b>>=1,a=a*a%c)if(b&1)ans=ans*a%c;return ans;}
inline void exgcd(ll a,ll b,ll &x,ll &y){if(!b)x=1,y=0;else exgcd(b,a%b,y,x),y-=(a/b)*x;}
int H,W,K;
string s[15];
int _1(int n){
    int a=0;
    while(n)a++,n&=n-1;
    return a;
}
int main(){
    //IN
    cin>>H>>W>>K;
    for(int i=0;i<H;i++)cin>>s[i];
    int ans=N;
    for(int bit=0;bit<(1<<H-1);bit++){
        int res=_1(bit);
        vector<int>v[H+1],sum(H+1,0);
        for(int j=0;j<W;j++){
            int num=0;
            for(int i=0;i<H;i++){
                num+=s[i][j]-'0';
                if(bit>>i&1){
                    v[i].push_back(num);
                    num=0;
                }else {
                    if(i==H-1)v[i].push_back(num);
                    else v[i].push_back(0);
                }
            } 
        }
        int last=-1;
        for(int j=0;j<W;j++){
            int ma=0;
            for(int i=0;i<H;i++){
                sum[i]+=v[i][j];
                ma=max(ma,sum[i]);
            }
            if(ma>K){
                j--;
                if(j==last){
                    res=1e5;break;
                }
                last=j;res++;
                for(int i=0;i<H;i++)sum[i]=0;
            }
        }
        ans=min(ans,res);
    }
    O(ans);
}

F.Knapsack for All Segments

如果只求区间[1,n]的方案数，就是裸的01背包计数。
现在是每一个区间，考虑对于只选a[i]，那么对于区间[1,i]的贡献是i,所以每次dp[0]++，即可。

#include<bits/stdc++.h>
using namespace std;
#define me(a,x) memset(a,x,sizeof(a))
#define sc scanf
#define pr printf
#define IN freopen("in.txt","r",stdin);
#define OUT freopen("out.txt","w",stdout);
typedef long long ll;
typedef unsigned long long ull;
const int N=1e6+6;
const int mod=998244353;
template<typename T>int O(T s){cout<<s<<endl;return 0;}
template<typename T>void db(T *bg,T *ed){while(bg!=ed)cout<<*bg++<<' ';pr("\n");}
template<typename T>void db(vector<T>it){for(auto i:it)cout<<i<<' ';pr("\n");}
inline ll mul_64(ll x,ll y,ll c){return (x*y-(ll)((long double)x/c*y)*c+c)%c;}
inline ll ksm(ll a,ll b,ll c){ll ans=1;for(;b;b>>=1,a=a*a%c)if(b&1)ans=ans*a%c;return ans;}
inline void exgcd(ll a,ll b,ll &x,ll &y){if(!b)x=1,y=0;else exgcd(b,a%b,y,x),y-=(a/b)*x;}
ll dp[3005];;
int n,s;
int a[N];
int main(){ 
    cin>>n>>s;
    for(int i=0;i++<n;sc("%d",&a[i]));
    ll ans=0;
    for(int i=1;i<=n;i++){
        dp[0]++;
        for(int j=s;j>=a[i];j--){
            dp[j]+=dp[j-a[i]];
            dp[j]%=mod;
        }
        ans+=dp[s];
        ans%=mod;
    }
    O(ans);
}