hanabi组队训练2

（ACM）贪心 （ACM）构造 （ACM）hanabi组队训练 （ACM）思维 201706

(题目链接)[http://codeforces.com/group/mbTSbPlZPV/contest/101341]

A. Streets of Working Lanterns - 2（贪心，实现）

题意

题解

• 输入时进行预处理，所有的串就变成y个')'，x个'('。
• 一开始左括号比右括号多k=0个。
• x-y>=0
  
  • 对于所有y小等于k的，选取x-y最大的。
• x-y<0
  
  • 对于某两个(x1,y1)(x2,y2)，如果取完1能够取2，那么k-y1+x1>=y2。
  • 于是贪心的策略是k-y1+x1-y2>=k-y2+x2-y1，化简结果是x1>=x2。

代码

#include<cstdio>
#include<cstring>
#include<queue>
#include<algorithm>
using namespace std;
const int N=200005;
char s[N];
int n;
int ans[N];
struct Node {
    int x,y,i;
}a[N];
bool cmp1(Node a,Node b) {
    return a.y<b.y;
}
bool cmp2(Node a,Node b) {
    return a.x>b.x;
}
void solve() {
    int cnt=0;
    ///x-y>=0
    sort(a+1,a+1+n,cmp1);
    int p=1,k=0;
    priority_queue<pair<int,int> > q;
    for(;;) {
        while(p<=n&&a[p].y<=k) {
            q.push(make_pair(a[p].x-a[p].y,a[p].i));
            ++p;
        }
        if(q.empty()||q.top().first<0) break;
        k=k+q.top().first;
        ans[++cnt]=q.top().second;
        q.pop();
    }
    ///x-y<0
    sort(a+1,a+1+n,cmp2);
    for(int i=1;i<=n;++i) {
        if(a[i].x-a[i].y>=0) continue;
        if(k>=a[i].y) {
            k=k+a[i].x-a[i].y;
            ans[++cnt]=a[i].i;
        } else {
            puts("NO");
            return ;
        }
    }
    ///print
    if(cnt!=n||k) {
        puts("NO");
        return ;
    }
    puts("YES");
    for(int i=1;i<=n;++i) printf("%d ",ans[i]);
    puts("");
}
int main() {
    while(~scanf("%d",&n)) {
        ///read
        for(int i=1;i<=n;++i) {
            scanf("%s",s);
            a[i].i=i;
            int len=strlen(s);
            for(int j=0;j<len;++j) {
                if(s[j]=='(') {
                    ++a[i].x;
                } else {
                    if(a[i].x) --a[i].x;
                    else ++a[i].y;
                }
            }
        }
        ///solve
        solve();
    }
    return 0;
}

F. Circuits（交互题，构造）

题意

题解

• 找出询问与真实的对应关系，0表示不可能存在。
• 构造一个栈，如果是+-/-+/--的情况，那么会消掉。
• 又因为+的个数大于-的。
• 于是栈最后剩下的是+++。
• 从表格可知，询问是++的情况才入栈。

代码

#include<cstdio>
#include<iostream>
using namespace std;
const int N=5005;
int sta[N],ans[N];
int main() {
    int n;
    while(~scanf("%d",&n)) {
        int p=1;sta[p]=1;
        for(int i=2;i<=n;++i) {
            if(p==0) {
                sta[++p]=i;
                continue;
            }
            printf("? %d %d\n",sta[p],i);
            cout.flush();
            char a,b;scanf(" %c %c",&a,&b);
            if(a=='+'&&b=='+') sta[++p]=i;
            else --p;
        }
        int x=sta[1];
        p=0;
        for(int i=1;i<=n;++i) {
            if(i==x) {
                ans[++p]=i;
                continue;
            }
            printf("? %d %d\n",x,i);
            cout.flush();
            char a,b;scanf(" %c %c",&a,&b);
            if(a=='+') ans[++p]=i;
        }
        printf("! %d",p);
        for(int i=1;i<=p;++i) printf(" %d",ans[i]);
        puts("");
        cout.flush();
    }
    return 0;
}

I. Matrix God（思维）

题意

• 判断方阵A*B是否等于C

题解

• 比赛的时候一直想FFT，赛后想想，如果可以用FFT做，大概就会要求输出矩阵C，而不是判断是否成立了。
• 用一个1×n的矩阵左乘，判断是否相等。做一次n2。可以用rand做100次。
• 直接(1,2,3,...)也行。
• 这样做大概有点哈希的意思吧。

代码

#include<cstdio>
typedef long long ll;
const int N=1005;
const ll mod=(1e9+7);
int n;
ll a[N][N],b[N][N],c[N][N];
ll d[N],e[N];
void solve() {
    for(int i=1;i<=n;++i) d[i]=i;
    for(int i=1;i<=n;++i) {
        e[i]=0;
        for(int j=1;j<=n;++j) {
            e[i]=(e[i]+d[j]*a[j][i]%mod)%mod;
        }
    }
    for(int i=1;i<=n;++i) {
        d[i]=0;
        for(int j=1;j<=n;++j) {
            d[i]=(d[i]+e[j]*b[j][i]%mod)%mod;
        }       
    }
    for(int i=1;i<=n;++i) {
        e[i]=0;
        for(int j=1;j<=n;++j) {
            e[i]=(e[i]+j*c[j][i]%mod)%mod;
        }
        if(d[i]!=e[i]) {
            puts("NO");
            return ;
        }
    }
    puts("YES");
}
int main() {
    while(~scanf("%d",&n)) {
        ///read
        for(int i=1;i<=n;++i) {
            for(int j=1;j<=n;++j) {
                scanf("%lld",&a[i][j]);
            }
        }
        for(int i=1;i<=n;++i) {
            for(int j=1;j<=n;++j) {
                scanf("%lld",&b[i][j]);
            }
        }
        for(int i=1;i<=n;++i) {
            for(int j=1;j<=n;++j) {
                scanf("%lld",&c[i][j]);
            }
        }
        ///solve
        solve();
    }
    return 0;
}

J. Catch the Monster（实现）

题意

• 一只怪兽，两个人，地图是一棵树。
• 怪兽能够预判人的所有行为。
• 初始人可以选择一个地方作为起点（两个人可以重合）。
• 怪兽速度远大于人。
• 人是否能抓到怪兽？（相遇即抓到）

题解

• 如果是蜈蚣图（主链之上有很多支链），必定yes
• 否则no
• 也就是说，所有的二度以上的点都在一条链上。
• 对每个点判断，它的子树至多两个拥有三度点。

代码

#include<cstdio>
#include<vector>
#include<cstring>
using namespace std;
const int N=200005;
vector<int> G[N];
bool ans;
int deg[N],cnt[N];
void dfs1(int u,int fa) {
    cnt[u]=(deg[u]>=3);
    int sz=G[u].size();
    for(int i=0;i<sz;++i) {
        int v=G[u][i];
        if(v==fa) continue;
        dfs1(v,u);
        cnt[u]+=cnt[v];
    }
}
void dfs2(int u,int fa) {
    if(!ans) return ;
    int res=(bool)(cnt[1]-cnt[u]);
    int sz=G[u].size();
    for(int i=0;i<sz;++i) {
        int v=G[u][i];
        if(v==fa) continue;
        dfs2(v,u);
        if(cnt[v]) ++res;
    }
    if(res>2) {
        ans=0;
        return ;
    }
}
int main() {
    int n;
    while(~scanf("%d",&n)) {
        ///init
        memset(deg,0,sizeof(deg));
        memset(cnt,0,sizeof(cnt));
        for(int i=1;i<=n;++i) G[i].clear();
        ///read
        for(int i=1;i<n;++i) {
            int u,v;scanf("%d%d",&u,&v);
            ++deg[u];++deg[v];
            G[u].push_back(v);
            G[v].push_back(u);
        }
        ///solve
        dfs1(1,1);
        ans=1;
        dfs2(1,1);
        ///print
        if(ans) puts("YES");
        else puts("NO");
    }
    return 0;
}

K. Competitions（实现，dp）

题意

题解

• dp

代码

#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
typedef long long ll;
const int N=200005;
struct Node {
    int l,r,i;
    ll c;
    bool operator < (const Node &tmp) const {
        return r<tmp.r;
    }
}a[N];
struct D {
    ll c,len;
    bool operator < (const D &tmp) const {
        if(c==tmp.c) return len>tmp.len;
        return c<tmp.c;
    }
}d[N<<1];
int X[N<<1],now[N<<1],pre[N<<1],res[N];
int main() {
    int n;
    while(~scanf("%d",&n)) {
        ///init
        for(int i=0;i<=2*n;++i) d[i].c=d[i].len=0;
        memset(now,-1,sizeof(now));
        memset(pre,-1,sizeof(pre));
        ///read
        int cntx=0;
        for(int i=1;i<=n;++i) {
            int l,r;ll c;
            scanf("%d%d%lld",&l,&r,&c);
            a[i].l=l;a[i].r=r;
            a[i].c=c;a[i].i=i;
            X[++cntx]=l;X[++cntx]=r;
        }
        ///get X
        sort(X+1,X+1+cntx);
        cntx=unique(X+1,X+1+cntx)-X;
        ///solve
        sort(a+1,a+1+n);
        int ans = 0;
        for(int i=1,p=1;p<=n;++p) {
            int L=lower_bound(X+1,X+1+cntx,a[p].l)-X;
            int R=lower_bound(X+1,X+1+cntx,a[p].r)-X;
            for(;i<=cntx&&i<=R;++i) {
                d[i]=max(d[i],d[i-1]);
                if(d[i].c==d[i-1].c&&d[i].len==d[i-1].len) {
                    now[i]=now[i-1];
                    pre[i]=pre[i-1];
                }
            }
            D t = D{d[L].c+a[p].c,d[L].len+a[p].r-a[p].l};
            d[R]=max(t,d[R]);
            if(d[R].c==t.c&&d[R].len==t.len) {
                now[R]=a[p].i;
                pre[R]=L;
            } 
            if(d[ans]<d[R]) ans=R;
        }
        ///print
        int cnt=0;
        for(int i=ans;i!=-1&&now[i]!=-1;i=pre[i]) {
            res[++cnt]=now[i];
        }
        printf("%d ",cnt);
        printf("%lld %lld\n",d[ans].c,d[ans].len);
        sort(res+1,res+1+cnt);
        for(int i=1;i<=cnt;++i) printf("%d ",res[i]);
        puts("");
    }
    return 0;
}