天天看點
傳回

Codeforces Round #297 (Div. 2)——A.B.C.D.E

http://codeforces.com/contest/525

A. Vitaliy and Pie

從左到右模拟一下

#include<bits/stdc++.h>
const int MAXN=;
using namespace std;
string s;
int n;
int key[MAXN];
int main()
{
    scanf("%d",&n);
    cin>>s;
    int l=s.length();
    int cnt=;
    for(int i=;i<l;++i){
        if(!(i&)) key[s[i]-'a']++;
        else{
            if(key[s[i]-'A']) key[s[i]-'A']--;
            else cnt++;
        }
    }
    printf("%d\n",cnt);
    return ;
}

B. Pasha and String

題目描述：

給定一個字元串s，然後m個操作，對區間[ai,|s|-ai+1]進行翻轉，求最後所得的字元串s’

1.可以用splay，貼個模闆就行了

2.用一個rev标記預先記錄每個位置翻轉的次數，然後從位置i~n/2，對每個位置的rev進行判定，swap(s[i],s[l-i+1])

#include<bits/stdc++.h>
const int MAXN=;
using namespace std;
int n;
int sum[MAXN];
char s[MAXN];
int main()
{
    scanf("%s",s);
    scanf("%d",&n);
    int x;
    for(int i=;i<=n;++i){
        scanf("%d",&x);
        sum[x]^=;
    }
    int l=strlen(s);
    int flag=;
    for(int i=;i<=l/;++i){
        flag^=sum[i];
        if(flag){
            swap(s[i-],s[l-i]);
        }
    }
    cout<<s<<endl;
    return ;
}

splay：

#include<bits/stdc++.h>
#define Key_value ch[ch[root][1]][0]
const int MAXN=;
const int INF=<<;
using namespace std;
int root,tot1,ch[MAXN][],key[MAXN],pre[MAXN];
int s[MAXN],tot2;
int rev[MAXN],size[MAXN];
int a[MAXN];
char str[MAXN];
int n,m;
void update_rev(int rt){
    if(!rt) return ;
    swap(ch[rt][],ch[rt][]);
    rev[rt]^=;
}
void push_up(int rt){
    int lson=ch[rt][],rson=ch[rt][];
    size[rt]=size[lson]+size[rson]+;
}
void push_down(int rt){
    if(rev[rt]){
        update_rev(ch[rt][]);
        update_rev(ch[rt][]);
        rev[rt]=;
    }
}
void NewNode(int &rt,int f,int k){
    if(tot2) rt=s[tot2--];
    else rt=++tot1;
    ch[rt][]=ch[rt][]=;
    pre[rt]=f;
    key[rt]=k;
    size[rt]=;
    rev[rt]=;
}
void build(int &rt,int l,int r,int f)
{
    if(l>r) return ;
    int mid=(l+r)>>;
    NewNode(rt,f,str[mid]-'a');
    build(ch[rt][],l,mid-,rt);
    build(ch[rt][],mid+,r,rt);
    push_up(rt);
}
void init()
{
    root=tot1=tot2=;
    rev[root]=ch[root][]=ch[root][]=pre[root]=size[root]=;
    NewNode(root,,-);
    NewNode(ch[root][],root,-);
    scanf("%s",str);
    n=strlen(str);
    build(Key_value,,n-,ch[root][]);
    push_up(ch[root][]);
    push_up(root);
}
void Rotate(int x,int kind)
{
    int y=pre[x];
    push_down(y);
    push_down(x);
    ch[y][!kind]=ch[x][kind];
    pre[ch[x][kind]]=y;
    if(pre[y])
        ch[pre[y]][ch[pre[y]][]==y]=x;
    pre[x]=pre[y];
    pre[y]=x;
    ch[x][kind]=y;
    push_up(y);
}
void Splay(int x,int goal)
{
    push_down(x);
    while(pre[x]!=goal) {
        if(pre[pre[x]]==goal) {
            Rotate(x,ch[pre[x]][]==x);
        } else {
            int y=pre[x];
            int kind=ch[pre[y]][]==y;
            if(ch[y][kind]==x) {
                Rotate(x,!kind);
                Rotate(x,kind);
            } else {
                Rotate(y,kind);
                Rotate(x,kind);
            }
        }
    }
    push_up(x);
    if(goal==) root=x;
}
int Get_kth(int rt,int k)
{
    push_down(rt);
    int z=size[ch[rt][]]+;
    if(z==k) return rt;
    if(z>k) return Get_kth(ch[rt][],k);
    else return Get_kth(ch[rt][],k-z);
}
void Reverse(int x,int y)
{
    Splay(Get_kth(root,x),);
    Splay(Get_kth(root,y+),root);
    update_rev(Key_value);
}
int cnt;
void InOrder(int rt)
{
    if(!rt) return ;
    push_down(rt);
    InOrder(ch[rt][]);
    if(cnt>=&&cnt<=n){
        printf("%c",key[rt]+'a');
    }
    cnt++;
    InOrder(ch[rt][]);

}
int main()
{
    init();
    int x;
    scanf("%d",&m);
    while(m--){
        scanf("%d",&x);
        Reverse(x,n-x+);
    }
    cnt=;
    InOrder(root);
    return ;
}

C. Ilya and Sticks

題目描述：

有n個木棍，每個木棍都有一個長度，求用其中的木棍組成一些矩形，求所有矩形的和的最大值。可以将每個木棍的長度減1

分析：根據題目，每個矩形隻能由4根木棍組成，那麼按木棍長度從大到小排序，每次比較相鄰的兩個木棍的長度差是否小于等于1，滿足則取出來

#include<bits/stdc++.h>
typedef long long ll;
const int MAXN=;
using namespace std;
ll len[MAXN];
vector<pair<ll,ll> > vl;
int n;
bool cmp(ll a,ll b){
    return a>b;
}
int main()
{
    scanf("%d",&n);
    for(int i=;i<n;++i) scanf("%I64d",&len[i]);
    sort(len,len+n,cmp);
    int cnt=;
    for(int i=;i<n;++i){
        if(len[i]-len[i+]<=){
            vl.push_back(make_pair(len[i],len[i+]));
            i++;
            cnt++;
        }
    }
    if(cnt>=){
        int l=vl.size();
        if(l&) l-=;
        ll sum=;
        for(int i=;i<l;i+=){
            sum+=vl[i].second*vl[i+].second;
        }
        printf("%I64d\n",sum);
    }else printf("0\n");
    return ;
}

D. Arthur and Walls

題目描述：

給定一個n*m的地圖，求将所有的由’.’組成的連通分量構成一個矩形，所需要删除的最少數量的’#’

取最小單元2*2的正方形，如果滿足隻有一個點是’#’,其餘都是’.’，則将’#’變成’.’

bfs

#include<bits/stdc++.h>
const int MAXN=;
using namespace std;
int n,m;
char pic[MAXN][MAXN];
queue<int> q;
int dx[]={-,-,-,,,,,};
int dy[]={-,,,-,,-,,};
bool check(int i,int j){
    if(pic[i][j]=='.'||i>n||i<||j>m||j<) return false;

    if(pic[i][j-]=='.'&&pic[i-][j-]=='.'&&pic[i-][j]=='.') return true;
    if(pic[i][j+]=='.'&&pic[i-][j]=='.'&&pic[i-][j+]=='.') return true;
    if(pic[i][j-]=='.'&&pic[i+][j]=='.'&&pic[i+][j-]=='.') return true;
    if(pic[i][j+]=='.'&&pic[i+][j]=='.'&&pic[i+][j+]=='.') return true;
    return false;
}
int main()
{
    scanf("%d%d",&n,&m);
    for(int i=;i<=n;++i){
        scanf("%s",pic[i]+);
    }
    for(int i=;i<=n;++i){
        for(int j=;j<=m;++j){
            if(check(i,j)){
                q.push(i);
                q.push(j);
            }
        }
    }
    while(!q.empty()){
        int x=q.front();q.pop();
        int y=q.front();q.pop();
        if(!check(x,y)) continue;
        pic[x][y]='.';
        for(int i=;i<;++i){
            int nx=x+dx[i];
            int ny=y+dy[i];
            if(check(nx,ny)){
                q.push(nx);
                q.push(ny);
            }
        }
    }
    for(int i=;i<=n;++i)
        printf("%s\n",pic[i]+);
    return ;
}

E. Anya and Cubes

題目描述：

有n個數，k個感歎号，求使用其中的某些數和感歎号，使它們的和為s的方案數

感歎号表示階乘

暴力枚舉，每個數有3種狀态，不取，取不使用！，取使用！

那麼總共有 325 種

中途相遇法：用map存儲前n/2種的所有可能值，然後再暴力後n/2的所有可能值，在map中查找，那麼時間就變成開根号了

詳見訓練指南58頁

#include<bits/stdc++.h>
typedef long long ll;
using namespace std;
int n,k;
ll s;
ll x[];
ll fac[];
ll ans;
map<ll,ll> mp[];
void init(){
    fac[]=;
    for(int i=;i<=;++i)
        fac[i]=fac[i-]*i;
}
void dfs_1(int i,int cnt,ll sum){
    if(cnt>k||sum>s) return ;
    if(i==n/){
        mp[cnt][sum]++;
        return ;
    }
    dfs_1(i+,cnt,sum);
    dfs_1(i+,cnt,sum+x[i]);
    if(x[i]<=){
        dfs_1(i+,cnt+,sum+fac[x[i]]);
    }
}
void dfs_2(int i,int cnt,ll sum){
    if(cnt>k||sum>s) return ;
    if(i==n){
        for(int j=;j+cnt<=k;++j){
            if(mp[j].count(s-sum)){
                ans+=mp[j][s-sum];
            }
        }
        return ;
    }
    dfs_2(i+,cnt,sum);
    dfs_2(i+,cnt,sum+x[i]);
    if(x[i]<=){
        dfs_2(i+,cnt+,sum+fac[x[i]]);
    }
}
int main()
{
    init();
    scanf("%d%d%I64d",&n,&k,&s);
    for(int i=;i<n;++i){
        scanf("%I64d",x+i);
    }
    dfs_1(,,);
    ans=;
    dfs_2(n/,,);
    printf("%I64d\n",ans);
    return ;
}
# Codeforces
上一篇: Codeforces Round #297 (Div. 2) C - Ilya and Sticks
下一篇: Codeforces Round #297 (Div. 2) C、D、E

繼續閱讀