2018-2019 XIX Open Cup, Grand Prix of Korea

E Electronic Circuit

题目链接
题意：给出n个点，m条边的图，要求判断是否存在源点、汇点使得图满足简单电路、仅存在串联和并联。
思路：对于a->b->c的路径可以压缩为a->b,不断压缩后判断是否只有源点和汇点，即为判断是否为简单电路。

#include <bits/stdc++.h>

#define maxn 100005
using namespace std;

int n,m,cnt;
int u,v;
set <int>G[maxn];
int book[maxn];

void del(int x){
    if(G[x].size()==2){
        book[x]=1;
        cnt--;
        int y = *G[x].begin();
        int z = *G[x].rbegin();
        G[y].erase(x);
        G[z].erase(x);
        G[y].insert(z);
        G[z].insert(y);
        if (!book[y]) del(y);
        if (!book[z]) del(z);
    }
}

void input(){
    scanf("%d%d",&n,&m);
    for(int i=1;i<=m;i++){
        scanf("%d%d",&u,&v);
        G[u].insert(v);
        G[v].insert(u);
    }
}

void solve(){
    cnt=n;
    for(int i=1;i<=n;i++)
    {
        if(!book[i]){
            del(i);
        }
    }

    printf(cnt==2?"Yes\n":"No\n");
}

int main(){
    input();
    solve();
}

F Fake Plastic Trees

题目链接
题意：要求构建一颗二叉树，每个节点的左节点的叶子数只能比右结点叶子数大于1或者等于。对于每个节点进行编号，要求节点编号大靠近根，节点编号小靠近叶子。若节点的左右节点连的相同可看作相同节点，对于节点hash后输出
思路：对于一个叶子节点为n的节点，若n为奇数，可以满足左节点叶子节点数为n/2+1，右结点为n/2。若n为偶数，可以分配左右节点的叶子节点数都为n/2。这个策略满足题目条件且满足节点个数不超过125。指数型下降。用dfs构造即可

#include <bits/stdc++.h>
#include<vector>

typedef long long ll;
using namespace std;

map <ll,int>ma;
map <ll,int>ind;
struct node{
    ll val;
    ll l,r;
}nod[205];
int cnt;

bool cmp(node a,node b){
    return a.val<b.val;
}

void dfs(ll n){
    if(ma[n])
        return;
    ma[n]=1;
    nod[cnt].val=n;
//    cout<<cnt<<' '<<n<<endl; 

    if(n==1)
    {
        nod[cnt].l=-1;
        nod[cnt].r=-1;
        cnt++;
        return;
    }

    if(n%2==0){
        nod[cnt].l=n/2;
        nod[cnt].r=n/2;    
        cnt++;
        dfs(max(1ll,n/2));
    }
    else{
        nod[cnt].l=n/2+1;
        nod[cnt].r=n/2;
        cnt++;
        dfs(n/2+1);
        dfs(n/2);
    }
}


int main(){
    int t;
    ll n;
    scanf("%d",&t);
    while(t--){
        cnt=0;
        ma.clear();
        ind.clear();

        scanf("%lld",&n);
        dfs(n);

        sort(nod,nod+cnt,cmp);

        printf("%d\n",cnt);
        ind[-1]=-1;
        for(int i=0;i<cnt;i++){
            ind[nod[i].val]=i;
            printf("%d %d\n",ind[nod[i].l],ind[nod[i].r]);
        }
        printf("%d\n",ind[nod[cnt-1].val]);
    }

    return 0;
}

H Fractions

题目链接
题意：给定A,B,C,D。x包含于[A,B]且y包含于[C,D]，求对于x和y，满足x/y化为最简后x+y<1000的(x,y)点对
思路：通过n^2的判断可以将1000以内满足互质且x+y<1000的数预处理出来。对于我们已知的点对(x,y)，寻找并且,经过化简得出并且。对于两个区间求交。

    #include<bits/stdc++.h>
    using namespace std;
    typedef long long ll;
    ll a[1004][1003];

    ll gcd(ll a, ll b) {
        return b ? gcd(b, a%b) : a;
    }
    void init() {
        for (ll i = 1; i <= 1000; i++) {
            for (ll j = 1; i + j < 1000; j++) {
                if (gcd(i, j) != 1)continue;
                a[i][++a[i][0]] = j;
            }
        }
    }

    ll solve(ll A, ll B, ll C, ll D) {
        ll ans = 0;
        for (ll i = 1; i <= 1000; i++) {
            for (ll jj = 1; jj <= a[i][0]; jj++) {
                ll j = a[i][jj];
                ll l1 = (A + i - 1) / i;
                ll l2 = (C + j - 1) /j;
                ll r1 = (B) / i;
                ll r2 = (D) / j;
    //            cout << l1 << " " << r1 << " " << l2 << " " << r2 << endl;
                ans += max(min(r1, r2) - max(l1, l2) + 1, 0ll);
                //cout << "*  " << ans << endl;
            }
        }                                                                                                                                                                                                                                                                                                                                                                                  
        return ans;
    }

    int main() {
        init();
        ll A, B, C, D;
        scanf("%lld%lld%lld%lld", &A, &B, &C, &D);
        printf("%lld\n", solve(A, B, C, D));
    }

I Game on Plane

题目链接
题意：对于n个点的正n边形，先手后手选择两个点连边，要求边不与之前边相交，且不能构成凸多边形。当不可连边时则失败。求先手后手谁赢
思路：SG函数

#include<iostream> 
#include<cstdio>
#include<cstring>
#include<map>
#include<vector> 
#include<set>
#include<queue>
#include<algorithm>
#include<string>
#include<cmath>
#include<stack>
#include<functional>
#include<bitset>
#define ll long long
#define maxn 100002
const int INF = 0x3f3f3f3f;

using namespace std;
int s[5002], sg[5002];
int main(void){
    int t, n, i, j;
    sg[1] = 0;
    sg[2] = 1;
    for(i = 3;i <= 5000;i++){
        for(j = 0;j <= 5000;j++){
            s[j] = 0;
        }
        for(j = 0;j * 2 <= i - 2;j++){
            s[sg[j] ^ sg[i - 2 - j]] = 1;
        }
        for(j = 0;j <= 5001;j++){
            if(!s[j]){
                sg[i] = j;
                break;
            }
        }
    }
    scanf("%d",&t);
    while(t--){
        scanf("%d",&n);
        if(sg[n]){
            puts("First");
        }
        else{
            puts("Second");
        }
    }
    return 0;
}

L Timsort

题目链接
题意：Timsort将区间分割为每个大小minrun以上的区域，并且保证在同一个区间里的数要么满足非递减、要么满足递减。当一个区间的数不满足非递减或者递减且小于minrun时，就用坏点。求最后多少个区间、多少个坏点。
思路：对于一个非递减或者递减区间、通过前两位数字即可得到。通过并查集可以快速寻找到最远的区间右点。

    #include <bits/stdc++.h>

    #define maxn 100005
    using namespace std;

    int fa1[maxn];
    int fa2[maxn];
    int a[maxn];
    int n;

    struct node{
        int l,r;
        int flag;
    }an[maxn];

    void init(int x){
        for(int i=1;i<=x;i++)
            fa1[i]=fa2[i]=i;

    }

    int find1(int x){
        return x==fa1[x]?x:fa1[x]=find1(fa1[x]); 
    }

    int find2(int x){
        return x==fa2[x]?x:fa2[x]=find2(fa2[x]);
    }

    void mix1(int x,int y){
        int fx=find1(x);
        int fy=find1(y);
        fa1[fx]=fy;
    }

    void mix2(int x,int y){
        int fx=find2(x);
        int fy=find2(y);
        fa2[fx]=fy;
    }

    void input(){
        scanf("%d",&n);
        init(n);
        int i;
        for(i=1;i<=n;i++){
            //a[i] = i & 1;
            scanf("%d",&a[i]);
        }    

        for(i=2;i<=n;i++){
            if(a[i]>=a[i-1])
                mix1(i-1,i);
            else
                mix2(i-1,i);
        }
    }

    void solve(){
        int q,x;
        scanf("%d",&q);
        //q = 100000;
        for(int i=1;i<=q;i++){
            //x = 2;
            scanf("%d",&x);

            if(an[x].flag){
                printf("%d %d\n",an[x].l,an[x].r);
                continue;
            }

            int ind1,ind2;
            int ans,bad;
            ans=bad=0;
            ind1=1;
            while(ind1<=n){
                ind2=min(n,ind1+x-1);
                int pos=max(find1(ind1),find2(ind1));

    //            cout<<ind1<<' '<<ind2<<' '<<pos<<endl;

                if(pos<ind2){
                    bad+=ind2-pos;
                    ind1=ind2+1;
                }else
                    ind1=pos+1;
                ans++;
            }

            printf("%d %d\n",ans,bad);
            an[x].l=ans;
            an[x].r=bad;
            an[x].flag=1;
        }
    }

    int main(){
        input();
        solve();
    }