2019牛客国庆集训派对day7

A 2016

题目链接
题意：对于给定的n和m，求1n和1m之间有多少个数对(a,b)，满足ab%2016==0
思路：对于一个数a，可以表示成（a/20162016+a%2016）的形式，那么a和b相乘是否为2016的倍数只需看右边模的部分。于是只需把所有模数的个数算出来就ok了，复杂度：2016^2

#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

using namespace std;
int num[2100][2100];
int main(void){
    ll ans, i, j, n, m;
    for(i = 0;i <= 2016;i++){
        num[0][i] = num[i][0] = 0;
    }
    for(i = 1;i <= 2016;i++){
        for(j = 1;j <= 2016;j++){
            if(i * j % 2016 == 0){
                num[i][j] = 1;
            }
            else{
                num[i][j] = 0;
            }
        }
    }
    for(i = 1;i <= 2016;i++){
        for(j = 1;j <= 2016;j++){
            num[i][j] += num[i - 1][j] + num[i][j - 1] - num[i - 1][j - 1];
        }
    }
    while(scanf("%lld %lld",&n,&m)!=EOF){
        ans = 1LL * ((n / 2016) * (m / 2016)) * num[2016][2016] + 1LL * (n / 2016) * num[m % 2016][2016] + 1LL * (m / 2016) * num[n % 2016][2016] + 1LL * num[n % 2016][m % 2016];
        printf("%lld\n",ans);
    }
    return 0;
}

B 有向无环图

题目链接
题意：对于给定的一个DAG，记录count(i,j)代表从i到j的路径个数，求
思路：拓扑跑图，对于拓扑完的点，将a累加上去。

#include <bits/stdc++.h>

#define maxn 100005
typedef long long ll;
using namespace std;
const int mod=1000000007;

int a[maxn],b[maxn];
int indeg[maxn];
int sum[maxn];
int n,m;

struct edge{
    int to,next;
};

int head[maxn];
edge G[maxn];
int edgeNum;

void add_edge(int u,int v){
    G[edgeNum].to=v;
    G[edgeNum].next=head[u];
    head[u]=edgeNum++;
}

struct node{
    int index;
    int val;
};

void topo(){

    queue <node>q;
    for(int i=1;i<=n;i++){
        if(!indeg[i])
            q.push((node){i,a[i]});
    }

    ll ans=0;
    while(!q.empty()){
        node f=q.front();
        q.pop();

        for(int i=head[f.index];i!=-1;i=G[i].next){
            int v=G[i].to;
            ans=(ans+1ll*f.val*b[v]%mod)%mod;
//          cout<<ans<<endl;
            sum[v]=(sum[v]+f.val)%mod;
            indeg[v]--;
            if(!indeg[v])
                q.push((node){v,(sum[v]+a[v])%mod});
        }
    }

    printf("%lld\n",ans);
}

void solve(){
    for(int i=1;i<=n;i++)
        scanf("%d%d",&a[i],&b[i]);

    int u,v;
    for(int i=0;i<m;i++){
        scanf("%d%d",&u,&v);
        add_edge(u,v);
        indeg[v]++;
    }

    topo();
}

int main(){
    while(scanf("%d%d",&n,&m)!=EOF){
        edgeNum=0;
        memset(head,-1,sizeof head);
        memset(indeg,0,sizeof indeg);
        memset(sum,0,sizeof sum);
        solve();
    }
}

/*
4 3
1 2
3 4
5 6
7 8
1 3
2 3
3 4

3 3
1 2
3 4
5 6
1 2
1 3
2 3
*/

F 地铁

题目链接
题意：给定一个无向图，n个点，m条边。每条边连接a，b。花费t和一个额外值c。代表若从上一条边作为路径走此边，需要加上额外费用。问最小费用。
思路：dij跑的pair中存，路径长度和边的序号，把边当作点跑dij。就可以计算作为额外值的最小费用。

还有图片说明
神奇建图方法，但是被卡掉了。 

#include <bits/stdc++.h>

#define maxn 200005
#define inf 1e18
typedef long long ll;
typedef std::pair<ll,ll> P;
using namespace std;

ll n, m;
struct edge {
    ll to, next; ll cost, c;
};

ll dis[maxn];

ll head[maxn];
edge G[maxn << 1];
ll edgeNum;

void add_edge(ll u, ll v, ll w, ll c) {
    G[edgeNum].to = v;
    G[edgeNum].cost = w;
    G[edgeNum].c = c;
    G[edgeNum].next = head[u];
    head[u] = edgeNum++;
}

void dij()
{
    priority_queue<P, vector<P>, greater<P> >q;

    memset(dis, 0x3f, sizeof(dis));
    for(int i=head[1];i!=-1;i=G[i].next){
        dis[i]=G[i].cost;
        q.push(P(dis[i],i));
    }

    ll ans=inf;
    while (!q.empty())
    {
        P temp = q.top();
        q.pop();
        ll v = temp.second;
        if (dis[v]<temp.first)continue;  
        if(G[v].to==n) ans=min(ans,dis[v]);
//        cout<<ans<<' '<<dis[v]<<' '<<G[v].to<<' '<<n<<endl;
        for (ll i = head[G[v].to]; i != -1; i = G[i].next) {
            if (dis[i]>dis[v]+G[i].cost+abs(G[i].c-G[v].c)) {
                dis[i] = dis[v]+G[i].cost+abs(G[i].c-G[v].c);
                q.push( P(dis[i],i));
            }
        }
    }
    printf("%lld\n",ans);
}


int main() {
    ll a, b, c, t;
    while (scanf("%lld%lld", &n, &m) != EOF) {
        edgeNum = 0;
        memset(head, -1, sizeof head);
        for (ll i = 0; i<m; i++) {
            scanf("%lld%lld%lld%lld", &a, &b, &c, &t);
            add_edge(a, b, 1ll * t, 1ll * c);
            add_edge(b, a, 1ll * t, 1ll * c);
        }
       dij();
    }
}

G Parenthesis

题目链接
题意：给定一个已经匹配的括号序列，求对于每个x,y对，交换是否会产生不匹配情况
思路：将每一个(看作+1,)看作-1。求不匹配即为在区间[l,r-1]之间寻找<2或者<-2的值。用线段树即可。x,y需要排序。

#include <bits/stdc++.h>

#define maxn 100005
#define inf 0x3f3f3f3f
using namespace std;

int n,m;
char a[maxn];
int b[maxn];
int ans[maxn<<2];

void PushUp(int rt){
    ans[rt]=min(ans[rt<<1],ans[rt<<1|1]);
}

void Build(int l,int r,int rt){
    if(l==r){
        ans[rt]=b[l];
        return ;
    }

    int mid=(l+r)>>1;
    Build(l,mid,rt<<1);
    Build(mid+1,r,rt<<1|1);
    PushUp(rt);
}

int query(int L,int R,int l,int r,int rt){
    if(L<=l&&r<=R){
        return ans[rt];
    }

    int ANS=inf;
    int mid=(l+r)>>1;
    if(L<=mid) ANS=min(ANS,query(L,R,l,mid,rt<<1));
    if(R>mid) ANS=min(ANS,query(L,R,mid+1,r,rt<<1|1));
    return ANS;
}

void input(){
    scanf("%s",a);
    for(int i=0;i<n;i++){
        if(a[i]=='(')
            b[i+1]=b[i]+1;
        else
            b[i+1]=b[i]-1;
    }

//  for(int i=1;i<=n;i++)
//      cout<<b[i]<<endl;
    Build(1,n,1);
    int l,r;
    for(int i=0;i<m;i++){
        scanf("%d%d",&l,&r);

        if(l>r)
            swap(l,r);

        if(a[l-1]==a[r-1]){
            puts("Yes");
            continue;
        }

        int res=query(l,r-1,1,n,1);
//      printf("%d\n",res);
        if(a[l-1]=='('){
            if(res<2)
                puts("No");
            else
                puts("Yes");   
        }else
        {
            if(res+2<0)
                puts("No");
            else
                puts("Yes");
        }
    }
}

int main(){
    while(scanf("%d%d",&n,&m)!=EOF){
        input();
//      solve();
    }
}

J 三角形和矩形

题目链接
题意：给定一个三角形和一个矩形，求交的面积
思路：旋转、翻转已有的三角形和矩形，特判各种情况

#include <bits/stdc++.h>

using namespace std;

double x[5],y[5];
double gety(double a,double x1,double y1)
{
    return y1-y1/x1*a;
}
double getx(double b,double x1,double y1)
{
    return x1-x1/y1*b;
}
int main(){
    while(scanf("%lf%lf",&x[1],&y[1])!=EOF){
        for(int i=2;i<=4;i++){
            scanf("%lf%lf",&x[i],&y[i]);
            x[i]-=x[1];
            y[i]-=y[1];
        }

        if(x[2]<0){
            for(int i=2;i<=4;i++){
                x[i]=-x[i];
            }
        }

        if(y[2]<0){
            for(int i=2;i<=4;i++){
                y[i]=-y[i];
            }
        }

        if(x[3]>x[4])
            swap(x[3],x[4]);
        if(y[3]>y[4])
            swap(y[3],y[4]);

        x[3]=max(x[3],0.0);
        y[3]=max(y[3],0.0);

        x[4]=min(x[4],x[2]);
        y[4]=min(y[4],y[2]);

        double ans;
        if(x[4]<=0||y[4]<=0||x[3]*y[2]+y[3]*x[2]-x[2]*y[2]>=0)
            ans=0;
        else if(x[4]*y[2]+y[4]*x[2]-x[2]*y[2]<=0)
            ans=(x[4]-x[3])*(y[4]-y[3]);       
        else{
            x[4]=min(x[4],getx(y[3],x[2],y[2]));
            y[4]=min(y[4],gety(x[3],x[2],y[2]));

            double X=getx(y[4],x[2],y[2]);
            double Y=gety(x[4],x[2],y[2]);
            ans=(x[4]-x[3])*(y[4]-y[3])-(x[4]-X)*(y[4]-Y)/2.0;
        }
        printf("%.10lf\n",ans);
    }
}