2019牛客国庆集训派对day5

A Simple Arithmetic

题目链接
题意：求向下取整的 a/b
思路：精度问题python莽过
还可以c++和long double计算
图片说明

try:
    while True:
        s = input()
        a,b=map(int,s.split())
        print(a//b)
except EOFError:
    pass

D Dynamic Graph

题目链接
题意：给你有向无环图，一种操作对于一个点进行翻转，求点对能到达的。
思路：topo+搜索，用bitset存关系，复杂度n^2

#include <bits/stdc++.h>

#define maxn 305
using namespace std;

int deg[maxn];
vector <int>g[maxn];
int color[maxn];
int vis[maxn];
bitset<maxn>p[maxn];

void dfs(int x){
    if(vis[x])return;
    vis[x]=1;

    p[x].reset();
    for(int i=0;i<g[x].size();i++){
        int v=g[x][i];
        dfs(v);
        if(!color[x]&&!color[v]){
            p[x]|=p[v];
            p[x][v]=1;    
        }        
    }
}

int main(){
    int n,m,q;
    while(scanf("%d%d%d",&n,&m,&q)!=EOF){
        for(int i=1;i<=n;i++){
            g[i].clear();
            deg[i]=color[i]=0;
        }

        int u,v;
        for(int i=0;i<m;i++){
            scanf("%d%d",&u,&v);
            g[u].push_back(v);
            deg[v]++;
        }

        while(q--){
            int x;
            scanf("%d",&x);
            color[x]^=1;
            memset(vis,0,sizeof vis);

            for(int i=1;i<=n;i++)
                if(deg[i]==0)
                    dfs(i);

            int ans=0;
            for(int i=1;i<=n;i++)
                ans+=p[i].count();
            printf("%d\n",ans);
        }
    }
}

E Longest Increasing Subsequence

题目链接
题意：定义Bi是原序列A删除第i个元素的序列，定义LIS是原LIS的f[i]数组的异或和。求每个Bi的LIS。
思路：先n^2跑出LIS中的F[i]和建边。枚举每个点topo进行O(n)的跑总时间复杂度n^2

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll maxn = 1e5 + 5;
const ll mod = 1e9 + 7;

int a[maxn];
int f[maxn];
int t[maxn];
int indeg[maxn];
int deg[maxn];
int n;
vector <int>G[maxn];

void get_LIS(){
    int i,j;
    for(i=1;i<=n;i++){
        f[i]=1;
        for(j=1;j<=i-1;j++){
            if(a[j]<a[i])
            {
                if(f[j]+1>f[i]){
                    f[i]=f[j]+1;
                }
            }
        }
    }
    for(i=1;i<=n;i++){
        for(j=1;j<=i-1;j++){
            if(f[j] + 1 == f[i]&&a[i] > a[j]){
                G[j].push_back(i);
                indeg[i]++;
//              cout<<j<<" "<<i<<endl;
            }
        }
    }  
}

void topo(int x){
    queue <int>q;
    q.push(x);

    while(!q.empty()){
        int f=q.front();
        q.pop();

        for(int i=0;i<G[f].size();i++){
            int v=G[f][i];
            deg[v]--;
            if(deg[v]==0){
                q.push(v);
                t[v]--;
            }
        }
    }
}

int main() {
    while(scanf("%d", &n)!=EOF){
        int i,j;
        for (i = 1; i <= n; i++) {
            scanf("%d", &a[i]);
            G[i].clear();
        }
        memset(indeg,0,sizeof indeg);


        get_LIS();

        for(i=1;i<=n;i++){

            for(j=1;j<=n;j++){
                t[j]=f[j];
                deg[j]=indeg[j];
            }

            topo(i);

//          for(int j=1;j<=n;j++){
//              if(j==i)continue;
//              printf("%d ",t[j]);
//          }
//          printf("\n");

            int ans;
            int flag=0;
            for(int j=1;j<=n;j++){
                if(j==i)continue;
                if(!flag)
                {
                    ans=t[j]*t[j];
                    flag=1;
                }else
                    ans=ans^(t[j]*t[j]);
            }

            printf("%d%c",ans,i==n?'\n':' ');
        }
    }
}

F Simple Algebra

题目链接
题意：求满足对于任意x，y使得 $f(x,y)=a*x^2+b*x*y+c*y^2 >=0$ 的a，b，c
思路：对于a和c任意一个大于0，可以转换为4ac-b*b>=0。若a和c任意一个小于0，都可以找出反例，即无解。当a=0且c=0时，只有b=0特判即可。

#include <bits/stdc++.h>

using namespace std;

int a,b,c;

void solve(){
    if((a>0||c>0))
    {
        if(4*a*c-b*b>=0)
            puts("Yes");
        else
            puts("No");
    }else if(a<0||c<0){
        puts("No");
    }else{
        if(b==0)
            puts("Yes");
        else
            puts("No");
    }

}

int main(){
    while(scanf("%d%d%d",&a,&b,&c)!=EOF){
        solve();
    }  
}

G 2017

题目链接
题意：给出a,b,c,d。求a<x<b并且c<y<d中x*y为2017倍数的个数
思路：当一个数为2017倍数，另一个为任意值都可。容斥。

#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 main(void){
    ll a, b, c, d, e, f;
    while(scanf("%lld %lld %lld %lld",&a,&b,&c,&d)!=EOF){
        e = (b / 2017 * 2017 - (a - 1) / 2017 * 2017) / 2017;
        f = (d / 2017 * 2017 - (c - 1) / 2017 * 2017) / 2017;
        printf("%lld\n",e * (d - c + 1) - e * f + f * (b - a + 1));
    }
    return 0;
}

K 2017 Revenge

题目链接
题意：给出n个数，选若干个满足乘积mod2017=r。问多少种方案。
思路：bitset优化dp，待补

L Nice Trick

题目链接
题意：给出三元式和计算方法，求四元式的计算值。
思路：模出样例，前缀和处理。

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
const ll maxn = 1e5 + 5;
const ll mod = 1e9 + 7;
ll a[maxn];
ll s1[maxn];
ll s2[maxn];
ll s3[maxn];
ll S[maxn];


ll qpow(ll A, ll B) {
    ll t = 1;
    while (B) {
        if ((B & 1)) {
            t = t * A%mod;
        }
        A = A * A%mod;
        B = B >> 1;
    }
    return t;
}

int main() {
    ll n;
    while (~scanf("%lld", &n)) {
        for (ll i = 1; i <= n; i++) {
            scanf("%lld", &a[i]);
            s1[i] = (s1[i - 1] + a[i]) % mod;
            s2[i] = (s2[i - 1] + a[i] * a[i] % mod) % mod;
            s3[i] = (s3[i - 1] + a[i] * a[i] % mod* a[i] % mod) % mod;
            //cout << s1[i] << " " << s2[i] << " " << s3[i] << endl;
            S[i] = (s1[i] * s1[i] % mod * s1[i] % mod - 3 * s2[i] % mod * s1[i] % mod + mod + 2 * s3[i] % mod) % mod*qpow(6, mod - 2) % mod;
            //cout << i << " " << S[i] << endl;
        }
        ll ans = 0;
        for (int l = 3; l <= n; l++) {
            ans = (ans + a[l] * S[l - 1] % mod) % mod;
        }
        cout << ans << endl;
    }
}