2019 ccpc 秦皇岛

柔情只为你懂 2023-06-03 02:53 14阅读 0赞

## D ##

如果1/n是有限小数，不停乘以10，一定在有限次之后成为一个整数。

10的质因子只有2和5，只要保证分母的质因子只有2和5即可

## F ##

仙人掌，环之间不相互影响，一个环至少删掉一条边，链无所谓，分别计算乘法原理合并

## I ##

和之前做过的一个题很像，但是那个题需要贪心的性质为支撑，这个dp直接做就行了

## J ##

倒过来做kmp找循环节

## A ##

直角三角形，就要看直角边在哪个点上，分两种情况讨论，然后围绕着直角点极角排序，找垂直的边。

#pragma GCC optimize(2)
    #include <iostream>
    #include <cstdio>
    #include <string>
    #include <cstring>
    #include <algorithm>
    #include <cmath>
    #include <stack>
    #include <vector>
    #include <set>
    #include <cmath>
    #include <queue>
    #include <map>
    #include <ctime>
    #define ll long long
    #define ld double
    #define lson rt << 1, l, m
    #define pi acos(-1)
    #define rson rt << 1 | 1, m + 1, r
    #define fo(i, l, r) for (int i = l; i <= r; i++)
    #define fd(i, l, r) for (int i = r; i >= l; i--)
    #define mem(x) memset(x, 0, sizeof(x))
    #define eps 1e-7
    using namespace std;
    const ll maxn = 4050;
    const ll mod = 998244353;
    ll read()
    {
        ll x = 0, f = 1;
        char ch = getchar();
        while (!(ch >= '0' && ch <= '9'))
        {
            if (ch == '-')
                f = -1;
            ch = getchar();
        };
        while (ch >= '0' && ch <= '9')
        {
            x = x * 10 + (ch - '0');
            ch = getchar();
        };
        return x * f;
    }
    struct Point
    {
        ll x, y;
        int isq,id;
        Point() {}
        Point(ll _x, ll _y)
        {
            x = _x;
            y = _y;
        }
        ll operator^(const Point &b) const
        {
            return x * b.y - y * b.x;
        }
        ll operator*(const Point &b) const
        {
            return x * b.x + y * b.y;
        }
        Point operator-(const Point &b) const
        {
            return Point(x - b.x, y - b.y);
        }
        Point operator+(const Point &b) const
        {
            return Point(x + b.x, y + b.y);
        }
        Point rotleft(){
            return Point(-y,x);
        }
        Point rotright(){
            return Point(y,-x);
        }
        int getfield(){
            if(x>0&&y>=0)return 1;
            if(x<=0&&y>0)return 2;
            if(x<0&&y<=0)return 3;
            if(x>=0&&y<0)return 4;
            return 5;
        }
    } ns[maxn], tmp[maxn],qs[maxn], now;
    struct cmp
    {
        Point p;
        cmp(const Point &p0){p = p0;}
        bool operator()(const Point &aa,const Point &bb)
        {
            Point a = aa-p,b = bb-p;
            if(a.getfield() != b.getfield()){
                return a.getfield() < b.getfield();
            }else{
                return (a^b)>0;
            }
        }
    };
    int n, q;
    ll ans[maxn];
    ll sum[maxn];
    int main()
    {
        while (scanf("%d%d", &n, &q) != EOF)
        {
            mem(ans);
            fo(i, 1, n)
            {
                scanf("%lld%lld",&ns[i].x,&ns[i].y);
                ns[i].isq=0;ns[i].id=i;
                tmp[i]=ns[i];
            }
            fo(i, 1, q)
            {
                scanf("%lld%lld",&qs[i].x,&qs[i].y);
                qs[i].isq=1;qs[i].id=i;
                now = qs[i];
                sort(ns + 1, ns + 1 + n, cmp(now));
                fo(j,1,n){
                    now=(ns[j]-qs[i]).rotleft();
                    now=qs[i]+now;
                    int ret = upper_bound(ns+1,ns+1+n,now,cmp(qs[i])) - lower_bound(ns+1,ns+1+n,now,cmp(qs[i]));
                    ans[i] += ret;
                }
            }
            fo(i,1,q){
                ns[n+i]=qs[i];
            }
            fo(i,1,n){
                now = tmp[i];
                sort(ns+1,ns+1+n+q,cmp(tmp[i]));
                fo(j,1,n+q){
                    if(!ns[j].isq&&ns[j].id!=now.id)sum[j]=sum[j-1]+1;
                    else sum[j]=sum[j-1];
                }
                fo(j,1,n+q){
                    if(!ns[j].isq)continue;
                    now=(ns[j]-tmp[i]).rotleft();
                    now=tmp[i]+now;
                    ans[ns[j].id] += sum[upper_bound(ns+1,ns+1+n+q,now,cmp(tmp[i]))-ns-1] - sum[lower_bound(ns+1,ns+1+n+q,now,cmp(tmp[i]))-ns-1];
                    now=(ns[j]-tmp[i]).rotright();
                    now=tmp[i]+now;
                    ans[ns[j].id] += sum[upper_bound(ns+1,ns+1+n+q,now,cmp(tmp[i]))-ns-1] - sum[lower_bound(ns+1,ns+1+n+q,now,cmp(tmp[i]))-ns-1];
                }
            }
            fo(i,1,q) printf("%lld\n",ans[i]);
        }
        return 0;
    }

##  E ##

给某些节点一个通过量的限制，从某些点出发、一些终点，可以向网络流的方向考虑，如何建图？

分析性质，假如说一个机器人从格点的一个边进入，再从某个边出，如果有人跟他反着来，则必然会逆着他走的路到第一行。

如果有人顺着它的路线走，那么会跟他走进同一个终点。

也就是说，如果这个节点，它拐弯了，那就只能一个机器人走一次。

如果它没拐弯，横着走过去之后，竖着走过去不会和原来横着走的路径有同样或者相反的结果，也就是能走两次。

拆点，把每个点拆成横竖两个点，相邻的恒竖相连，可以走2次，同一个点横竖相连，割这个边就说明在这个点放了转向器，只能走一次。

#include <iostream>
    #include <cstdio>
    #include <string>
    #include <cstring>
    #include <algorithm>
    #include <cmath>
    #include <queue>
    #include <vector>
    #define fo(i, l, r) for (int i = l; i <= r; i++)
    #define fd(i, l, r) for (int i = r; i >= l; i--)
    #define mem(x) memset(x, 0, sizeof(x))
    #define ll long long
    using namespace std;
    const int maxn = 300050;
    ll read()
    {
        ll x = 0, f = 1;
        char ch = getchar();
        while (!(ch >= '0' && ch <= '9'))
        {
            if (ch == '-')
                f = -1;
            ch = getchar();
        };
        while (ch >= '0' && ch <= '9')
        {
            x = x * 10 + (ch - '0');
            ch = getchar();
        };
        return x * f;
    }
    const int MAXN = 200010; //点数的最大值
    const int MAXM = 1600010; //边数的最大值
    const int INF = 0x3f3f3f3f;
    struct Edge
    {
        int to, next, cap, flow;
    } edge[MAXM]; //注意是 MAXM
    int tol;
    int head[MAXN];
    int gap[MAXN], dep[MAXN], cur[MAXN];
    void init()
    {
        tol = 0;
        memset(head,-1, sizeof(head));
    }
    void addedge(int u, int v, int w, int rw = 0)
    {
        edge[tol].to = v;
        edge[tol].cap = w;
        edge[tol].flow = 0;
        edge[tol].next = head[u];
        head[u] = tol++;
        edge[tol].to = u;
        edge[tol].cap = rw;
        edge[tol].flow = 0;
        edge[tol].next = head[v];
        head[v] = tol++;
    }
    int Q[MAXN];
    void BFS(int start, int end)
    {
        memset(dep,-1, sizeof(dep));
        memset(gap, 0, sizeof(gap));
        gap[0] = 1;
        int front = 0, rear = 0;
        dep[end] = 0;
        Q[rear++] = end;
        while (front != rear)
        {
            int u = Q[front++];
            for (int i = head[u]; i != -1; i = edge[i].next)
            {
                int v = edge[i].to;
                if (dep[v] != -1)
                    continue;
                Q[rear++] = v;
                dep[v] = dep[u] + 1;
                gap[dep[v]]++;
            }
        }
    }
    int S[MAXN];
    int sap(int start, int end, int N)
    {
        BFS(start, end);
        memcpy(cur, head, sizeof(head));
        int top = 0;
        int u = start;
        int ans = 0;
        while (dep[start] < N)
        {
            if (u == end)
            {
                int Min = INF;
                int inser;
                for (int i = 0; i < top; i++)
                    if (Min > edge[S[i]].cap - edge[S[i]].flow)
                    {
                        Min = edge[S[i]].cap - edge[S[i]].flow;
                        inser = i;
                    }
                for (int i = 0; i < top; i++)
                {
                    edge[S[i]].flow += Min;
                    edge[S[i] ^ 1].flow -= Min;
                }
                ans += Min;
                top = inser;
                u = edge[S[top] ^ 1].to;
                continue;
            }
            bool flag = false;
            int v;
            for (int i = cur[u]; i != -1; i = edge[i].next)
            {
                v = edge[i].to;
                if (edge[i].cap - edge[i].flow && dep[v] + 1 == dep[u])
                {
                    flag = true;
                    cur[u] = i;
                    break;
                }
            }
            if (flag)
            {
                S[top++] = cur[u];
                u = v;
                continue;
            }
            int Min = N;
            for (int i = head[u]; i != -1; i = edge[i].next)
                if (edge[i].cap - edge[i].flow && dep[edge[i].to] < Min)
                {
                    Min = dep[edge[i].to];
                    cur[u] = i;
                }
            gap[dep[u]]--;
            if (!gap[dep[u]])
                return ans;
            dep[u] = Min + 1;
            gap[dep[u]]++;
            if (u != start)
                u = edge[S[--top] ^ 1].to;
        }
        return ans;
    }
    int n,m,a,b;
    char mp[105][105];
    inline int tran(int y,int x,int dir){
        int t = (y-1)*m+x;
        if(dir) t+=n*m;
        return t;
    }
    inline bool jud(int y,int x){
        return y>=1&&y<=n&&x>=1&&x<=m&&mp[y][x]=='0';
    }
    int main()
    {
        int T=read();
        while(T--){
            init();
            n=read();m=read();a=read();b=read();
            fo(i,1,n){
                scanf("%s",mp[i]+1);
            }
            fo(i,1,n){
                fo(j,1,m){
                    if(jud(i-1,j)) addedge(tran(i,j,0),tran(i-1,j,0),1);
                    if(jud(i+1,j)) addedge(tran(i,j,0),tran(i+1,j,0),1);
                    if(jud(i,j-1)) addedge(tran(i,j,1),tran(i,j-1,1),1);
                    if(jud(i,j+1)) addedge(tran(i,j,1),tran(i,j+1,1),1);
                    addedge(tran(i,j,0),tran(i,j,1),1);
                    addedge(tran(i,j,1),tran(i,j,0),1);
                }
            }
            int u;
            fo(i,1,a){
                u=read();
                addedge(0,tran(1,u,0),1);
            }
            fo(i,1,b){
                u=read();
                addedge(tran(n,u,0),n*m*2+1,1);
            }
            if(sap(0,n*m*2+1,n*m*2+2)==a){
                printf("Yes\n");
            }else{
                printf("No\n");
            }
        }    
        return 0;
    }

转载于:https://www.cnblogs.com/hyfer/p/11612825.html