Regionals 2015 :: Asia - Taipei 部分题解

【第3次区域赛训练赛】最终做了6题，完全是因为这场比赛水的缘故。。。赛后又补了个题，现在来写一下这7题的题解，总结一下。

【A - Parentheses】https://icpcarchive.ecs.baylor.edu/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=5476

【题意】括号匹配问题，求最少的翻转(左右括号转换)操作使得原串合法.

【解题方法】用栈来模拟即可。栈模拟判断当前串是否合法：①. 如果当前是'('，直接入栈.②. 如果当前是')'，如果栈非空，则弹出一个'('; 如果栈空就把当前的')'变成'('入栈.最后的结果栈中肯定全是'('，那么把其中的一半变成')'即可.

【AC 代码】

【B - Linear】 Ecosystem https://icpcarchive.ecs.baylor.edu/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=5477

【题意】对一个k元向量, 每次左乘一个k*k的矩阵得到新的向量.问经过一定次数的左乘后，能否使得该向量不再变化. (同时要求此时向量非零)

【解题方法】设初始向量为A，矩阵为P.由于每次矩阵P都是左乘A, 那么可以把若干个P合并. 则题目的条件是：化简为：由于要求所以 P-1 必须不可逆.可以直接用高斯消元求P-1的秩，判断是否可逆（满秩即可逆）.

【AC 代码】

#include <math.h>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <iostream>
#include <algorithm>
using namespace std;
const double eps=1e-10;
const int maxn = 500;
double a[maxn][maxn];
int guass(int n)
{
    int res=0,r=0;
    for(int i=0; i<n; i++)
    {
        for(int j=r; j<n; j++) if(fabs(a[j][i])>eps)
        {
            for(int k=i; k<n; k++) swap(a[j][k],a[r][k]);
            break;
        }
        if(fabs(a[r][i])<eps){
            res++;continue;
        }
        for(int j=0; j<n; j++) if(j!=r&&fabs(a[j][i])>eps)
        {
            double tmp=a[j][i]/a[r][i];
            for(int k=i; k<n; k++) a[j][k]-=tmp*a[r][k];
        }
        r++;
    }
    return res;
}

int main()
{
    int n;
    int T,cas=0;
    scanf("%d",&T);
    while(T--)
    {
        ++cas;
        scanf("%d",&n);
        for(int i=0; i<n; i++)
        {
            for(int j=0; j<n; j++){
                scanf("%lf",&a[i][j]);
            }
            a[i][i]-=1.0;
        }
        int ret=guass(n);
        if(ret) printf("1");
        else printf("0");
        if(cas==5)
        {
            if(T) printf("\n");
            cas=0;
        }
        else if(T){
            printf(" ");
        }
    }
    printf("\n");
    return 0;
}

【 C - Least Crucial Node】 https://icpcarchive.ecs.baylor.edu/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=5478

【题意】求标号最小的最大割点.(删除该点后，指定点#sink能到达的点数减少最多).

【解题方法】大概是求割点，维护size，判断一下就好，队友写的，我不会图论（甩锅），不过貌似很简单的样子QAQ

【AC 代码】

#include<bits/stdc++.h>
using namespace std;
const int N= 110;
vector<int>v[N];
int vis[N],dfn[N],low[N],cut[N],bridge[N][N],sz[N];
void dfs(int u,int fa,int dep)
{
    vis[u]=1;
    dfn[u]=low[u]=dep;
    int children=0;
    for(int i=0;i<v[u].size();i++){
        int t=v[u][i];
        if(t!=fa&&vis[t]==1){
            if(dfn[t]<low[u]){
                low[u]=dfn[t];
            }
        }
        if(vis[t]==0){
            dfs(t,u,dep+1);
            children++;
            if(low[t]<low[u]) low[u]=low[t];
            if((fa==-1&&children>1)||(fa!=-1&&low[t]>=dfn[u])){
                cut[u]++;
            }
            if(low[t]>dfn[u]){
                bridge[u][t]=bridge[t][u]=1;
            }
        }
    }
    vis[u]=2;
}
void dfs1(int u)
{
    vis[u]=1;
    sz[u]=1;
    for(int i=0;i<v[u].size();i++){
        int ed=v[u][i];
        if(vis[ed]) continue;
        dfs1(ed);
        sz[u]+=sz[ed];
    }
}
int main()
{
    int n,m,x,y,st;
    while(~scanf("%d",&n)&&n){
    memset(bridge,0,sizeof(bridge));
    memset(vis,0,sizeof(vis));
    memset(cut,0,sizeof(cut));
    scanf("%d%d",&st,&m);
    for(int i=1;i<=n;i++) v[i].clear();
    while(m--){
        scanf("%d%d",&x,&y);
        v[x].push_back(y);
        v[y].push_back(x);
    }
    dfs(st,-1,0);
    memset(vis,0,sizeof(vis));
    memset(sz,0,sizeof(sz));
    dfs1(st);
    int ans,maxx=0;
    for(int i=1;i<=n;i++){
       // if(cut[i]) printf("%d\n",i);
        if(sz[i]>maxx&&cut[i]){
            maxx=sz[i];
            ans=i;
        }
    }
    printf("%d\n",ans);
    }
    return 0;
}

【 D - Discrete Logarithm Problem】 https://icpcarchive.ecs.baylor.edu/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=5479

【题意】<big>求一个x使得 a^x%p = b p为素数</big>

【解题方法】快速幂模拟一下就行啦，也可以暴力模拟，雀巢原理嘛。

【AC 代码】

【G - Maximum Cut Order】https://icpcarchive.ecs.baylor.edu/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=5482

【题意】大概读懂题，理解了，这题就完全是水题了。

【解题方法】不说了，代码很清楚了。

【AC代码】

#include<cstdio>
#include<cstring>
#include<queue>
using namespace std;
const int N =6e5;
int vis[N],ans[N],cnt,n,k;
struct node
{
    int x,y;
    friend bool operator < ( const node &a,const node &b)
    {
        if(a.y==b.y) return a.x>b.x;
        else return a.y<b.y;
    }
};
priority_queue<node>q;
void dfs(int u)
{
    ans[cnt++]=u;
    vis[u]=1;
    node t;
    if(u*2<=n&&vis[2*u]==0){
        t={2*u,u%k};
        q.push(t);
    }
    if((2*u+1)<=n&&vis[2*u+1]==0){
        t={2*u+1,(u+1)%k};
        q.push(t);
    }
    if(u/2>0&&vis[u/2]==0){
        t={u/2,(u-u/2)%k};
        q.push(t);
    }
    if(q.empty()) return ;
    t=q.top();
    q.pop();
    dfs(t.x);
}
int main()
{
    int T,st;
    scanf("%d",&T);
    while(T--){
        memset(vis,0,sizeof(vis));
        cnt=1;
        scanf("%d%d%d",&n,&st,&k);
        dfs(st);
        for(int i=1;i<=n;i++){
            if(i==1) printf("%d",ans[i]);
            else printf(" %d",ans[i]);
        }
        printf("\n");
    }
    return 0;
}

【 H - Separating Pebbles】 https://icpcarchive.ecs.baylor.edu/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=5483

【题意】给出平面上的两类点，判断是否能画一条直线将两类点完全分割开来.

【解题方法】N*N*N暴力即可。

【AC 代码】

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
const int maxn = 255;
struct point{
    int x,y,z;
    void read()
    {
        scanf("%d%d%d",&x,&y,&z);
    }
    bool operator<(const point &rhs) const{
        if(x==rhs.x) return y<rhs.y;
        return x<rhs.x;
    }
}a[maxn];
point subt(point a,point b)
{
    return point{a.x-b.x,a.y-b.y,a.z-b.z};
}
int xmult(point a,point b)
{
    return a.x*b.y-a.y*b.x;
}
int Cross(point a,point b,point c)//判断在直线的哪一侧
{
    return (b.x-a.x)*(c.y-a.y)-(b.y-a.y)*(c.x-a.x);
}
int cnt1,cnt2,n;
bool solve()
{
    bool jud=false;
    for(int i=1; i<=n; i++)
    {
        for(int j=1; j<=n; j++)
        {
            if(i==j) continue;
            int s1=0,s2=0;
            for(int k=1; k<=n; k++)
            {
                if(Cross(a[i],a[j],a[k])>0&&a[k].z==0) s1++;
                else if(Cross(a[i],a[j],a[k])>0&&a[k].z==1) s2++;
                else if(Cross(a[i],a[j],a[k])==0&&a[k].z==0) s1++;
                else if(Cross(a[i],a[j],a[k])==0&&a[k].z==1) s2++;
            }
            if(s1==cnt1&&s2==0) jud=true;
            if(s1==0&&s2==cnt2) jud=true;
        }
    }
    return jud;
}
int main()
{
    int T;
    scanf("%d",&T);
    while(T--)
    {
        scanf("%d",&n);
        cnt1=0,cnt2=0;
        for(int i=1; i<=n; i++)
        {
            a[i].read();
            if(a[i].z==0) cnt1++;
            else cnt2++;
        }
        sort(a+1,a+n+1);
        bool ***=false;
        point x=subt(a[1],a[2]);
        for(int i=2; i<=n; i++)
        {
            if(xmult(x,subt(a[1],a[i]))!=0) ***=true;
        }
        if(***==false)
        {
            int s1,s2;
            bool fff1,fff2;
            if(a[1].z==0) s1=0,fff1=1;
            else s2=0,fff2=1;
            for(int k=1; k<=n; k++)
            {
                if(fff1&&a[k].z==0) s1++;
                else break;
            }
            for(int k=1; k<=n; k++)
            {
                if(fff2&&a[k].z==1) s2++;
                else break;
            }
            if(s1==cnt1||s2==cnt2)
            {
                printf("1\n");
            }
            else
            {
                printf("0\n");
            }
        }
        else{
            bool jud=solve();
            if(jud) printf("1\n");
            else printf("0\n");
        }
    }
    return 0;
}

【 K - Robots】 https://icpcarchive.ecs.baylor.edu/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=5486

【题意】有一个基点和n个A机器m个B机器。A机器传输时间为x，B机器传输时间为y(x<y)，现在要把所有机器上的信息汇总传输给基点。而且同一时刻，每个机器只能传给另一个机器或者接受来自另一个机器的传输。基点一次只能接收一个机器的信息。求最小传输时间。

【解题方法】首先B机器要满，所以首先要把B机器都传出去。先选择一个机器传给基点，剩下的机器都传输给A机器（同时进行）。如果此时A机器还有空闲的，那么就两两互传，把信息整合到一台机器上。就是消耗时间的时候尽可能的调动所有可用的机器传输。

【PS】这道题是我今天赛后补得。

【AC 代码】

【ACMER 万岁】