牛客练习赛49_牛客博客

Problem A 筱玛爱地理

https://ac.nowcoder.com/acm/contest/946/A

题意：

题解：逆元+排序

C++版本一

/*
*@Author:   STZG
*@Language: C++
*/
#include <bits/stdc++.h>
#include<iostream>
#include<algorithm>
#include<cstdlib>
#include<cstring>
#include<cstdio>
#include<string>
#include<vector>
#include<bitset>
#include<queue>
#include<deque>
#include<stack>
#include<cmath>
#include<list>
#include<map>
#include<set>
//#define DEBUG
#define RI register int
#define endl "\n"
using namespace std;
typedef long long ll;
//typedef __int128 lll;
const int N=200000+10;
const int M=100000+10;
const int MOD=1e9+7;
const double PI = acos(-1.0);
const double EXP = 1E-8;
const int INF = 0x3f3f3f3f;
int t,n,m,k,p,l,r,u,v;
int ans,cnt,flag,temp,sum;
struct node{
    int v,e;
    bool operator<(const node &S)const{
        return (double)e/v>(double)S.e/S.v;
    }
}G[N];
ll POW(ll a,ll b=MOD-2,ll c=MOD){
    ll res=1;
    ll base=a%c;
    while(b){
        if(b&1)res=(res*base)%c;
        base=(base*base)%c;
        b>>=1;
    }
    return res;
}
int main()
{
#ifdef DEBUG
	freopen("input.in", "r", stdin);
	//freopen("output.out", "w", stdout);
#endif
    //ios::sync_with_stdio(false);
    //cin.tie(0);
    //cout.tie(0);
    scanf("%d",&n);
    for(int i=1;i<=n;i++)scanf("%d%d",&G[i].v,&G[i].e);
    sort(G+1,G+n+1);
    for(int i=1;i<=n;i++)cout<<G[i].e*POW(G[i].v)%MOD<<endl;

#ifdef DEBUG
	printf("Time cost : %lf s\n",(double)clock()/CLOCKS_PER_SEC);
#endif
    //cout << "Hello world!" << endl;
    return 0;
}

Problem B 筱玛爱阅读

https://ac.nowcoder.com/acm/contest/946/B

题意：

题解：

C++版本一

/*
*@Author:   STZG
*@Language: C++
*/
#include <bits/stdc++.h>
#include<iostream>
#include<algorithm>
#include<cstdlib>
#include<cstring>
#include<cstdio>
#include<string>
#include<vector>
#include<bitset>
#include<queue>
#include<deque>
#include<stack>
#include<cmath>
#include<list>
#include<map>
#include<set>
//#define DEBUG
#define RI register int
#define endl "\n"
using namespace std;
typedef long long ll;
//typedef __int128 lll;
const int N=100+10;
const int M=600000+10;
const int MOD=1e9+7;
const double PI = acos(-1.0);
const double EXP = 1E-8;
const int INF = 0x3f3f3f3f;
int t,n,m,k,p,l,r,u,v;
int ans,cnt,flag,temp,sum;
int f[1<<15],c[20];
int g[1<<15],sz[1<<15];
int main()
{
#ifdef DEBUG
	freopen("input.in", "r", stdin);
	//freopen("output.out", "w", stdout);
#endif
    //ios::sync_with_stdio(false);
    //cin.tie(0);
    //cout.tie(0);
    //scanf("%d",&t);
    //while(t--){
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++){
        scanf("%d",&c[i]);
        sum+=c[i];
    }
    sort(c+1,c+n+1);
    for(int i=1;i<=m;++i) {
        int s=0;
        scanf("%d",&k);
        for(int i=1;i<=k;++i)
            scanf("%d",&p),s|=(1<<(p-1));
        g[s]=1;
    }
    for(int i=1;i<(1<<n);++i) sz[i]=sz[(i-1)&i]+1;
    for(int i=0;i<(1<<n);++i) {
        int s=((1<<n)-1)^i;
        for(int j=s;j;j=(j-1)&s) if(g[j]) {
            f[i|j]=max(f[i|j],f[i]+c[sz[i]+1]);
        }
    }
    printf("%d\n",sum-f[(1<<n)-1]);
    //}

#ifdef DEBUG
	printf("Time cost : %lf s\n",(double)clock()/CLOCKS_PER_SEC);
#endif
    //cout << "Hello world!" << endl;
    return 0;
}

Problem C 筱玛爱历史

https://ac.nowcoder.com/acm/contest/946/C

题意：

题解：

C++版本一

Problem D 筱玛爱线段树

https://ac.nowcoder.com/acm/contest/946/D

题意：第一种操作对[l,r]区间内每幢房子塞入一个皮卡丘; 第二种操作对第l次到第r次的操作重复一遍。

题解：可以 O(n)维护两个差分数组，一个是针对重复操作的差分数组，一个是针对当前房子塞入皮卡丘的个数的差分数组。对第二个差分数组的每次修改的大小是当前操作重复操作次数。因为每一次第二种操作总是针对之前的操作，所以要倒着跑一遍。最后对针对当前房子塞入皮卡丘的个数的差分数组求个前缀和就好了。

C++版本一

/*
*@Author:   STZG
*@Language: C++
*/
#include <bits/stdc++.h>
#include<iostream>
#include<algorithm>
#include<cstdlib>
#include<cstring>
#include<cstdio>
#include<string>
#include<vector>
#include<bitset>
#include<queue>
#include<deque>
#include<stack>
#include<cmath>
#include<list>
#include<map>
#include<set>
//#define DEBUG
#define RI register int
#define endl "\n"
using namespace std;
typedef long long ll;
//typedef __int128 lll;
const int N=100000+10;
const int M=100000+10;
const int MOD=1e9+7;
const double PI = acos(-1.0);
const double EXP = 1E-8;
const int INF = 0x3f3f3f3f;
int t,n,m,k,p,l,r,u,v;
int ans,cnt,flag,temp,sum;
ll a[N],pre[N];
char str;
struct node{
    int l,r,op;
}e[N];
int main()
{
#ifdef DEBUG
	freopen("input.in", "r", stdin);
	//freopen("output.out", "w", stdout);
#endif
    //ios::sync_with_stdio(false);
    //cin.tie(0);
    //cout.tie(0);
    //scanf("%d",&t);
    while(~scanf("%d%d",&n,&m)){
        memset(pre,0,sizeof(pre));
        memset(a,0,sizeof(a));
        pre[m+1]++;
        pre[0]--;
        for(int i=1;i<=m;i++){
            scanf("%d%d%d",&e[i].op,&e[i].l,&e[i].r);
        }
        for(int i=m;i>=1;i--){
            pre[i]=(pre[i]+pre[i+1])%MOD;
            if(e[i].op!=1){
                pre[e[i].r]=(pre[e[i].r]+pre[i])%MOD;
                pre[e[i].l-1]=(pre[e[i].l-1]-pre[i]+MOD)%MOD;
            }else{
                a[e[i].l]=(a[e[i].l]+pre[i])%MOD;
                a[e[i].r+1]=(a[e[i].r+1]-pre[i]+MOD)%MOD;
                //cout<<e[i].l<<" "<<e[i].r<<" "<<pre[i]<<endl;
            }
        }
        for(int i=1;i<=n;i++){
            a[i]=(a[i]+a[i-1])%MOD;
        }
        for(int i=1;i<=n;i++){
            printf("%lld%c",a[i]," \n"[i==n]);
        }
    }

#ifdef DEBUG
	printf("Time cost : %lf s\n",(double)clock()/CLOCKS_PER_SEC);
#endif
    //cout << "Hello world!" << endl;
    return 0;
}

Problem E 筱玛爱游戏

https://ac.nowcoder.com/acm/contest/946/E

题意：
首先，桌面上一共有nn个数。

两个人轮流从桌面上取走一个数，并把这个数放入集合中。

如果在某次操作结束后，集合中存在一个异或和为00的非空子集，那么进行这次操作的人输。

如果全部取完，则最后操作的人赢。

题解：线性基

C++版本一

/*
*@Author:   STZG
*@Language: C++
*/
#include <bits/stdc++.h>
#include<iostream>
#include<algorithm>
#include<cstdlib>
#include<cstring>
#include<cstdio>
#include<string>
#include<vector>
#include<bitset>
#include<queue>
#include<deque>
#include<stack>
#include<cmath>
#include<list>
#include<map>
#include<set>
//#define DEBUG
#define RI register int
#define endl "\n"
using namespace std;
typedef long long ll;
//typedef __int128 lll;
const int N=100000+10;
const int M=100000+10;
const int MOD=1e9+7;
const double PI = acos(-1.0);
const double EXP = 1E-8;
const int INF = 0x3f3f3f3f;
int t,n,m,k,p,l,r,u,v;
int ans,cnt,flag,temp,sum;
ll a[N];
char str;
struct node{};
struct Linear_Basis{
    ll d[63],p[63],tot;
    void init(){
        tot=0;
        memset(d,0,sizeof(d));
        memset(p,0,sizeof(p));
    }
    bool ins(ll x){
        for(int i=62;i>=0;i--)
            if (x&(1ll<<i))
            {
                if (!d[i]) {d[i]=x;break;}
                x^=d[i];
            }
        return x>0;
    }
} LB;
int main()
{
#ifdef DEBUG
	freopen("input.in", "r", stdin);
	//freopen("output.out", "w", stdout);
#endif
    //ios::sync_with_stdio(false);
    //cin.tie(0);
    //cout.tie(0);
    //scanf("%d",&t);
    //while(t--){
    scanf("%d",&n);
    for(int i=1;i<=n;i++)scanf("%lld",&a[i]);
    for(int i=1;i<=n;i++){
        if(LB.ins(a[i]))ans++;
    }
    cout<<(ans&1?"First":"Second")<<endl;
    //}

#ifdef DEBUG
	printf("Time cost : %lf s\n",(double)clock()/CLOCKS_PER_SEC);
#endif
    //cout << "Hello world!" << endl;
    return 0;
}

Problem F 筱玛爱语文

https://ac.nowcoder.com/acm/contest/946/F

题意：

题解：

C++版本一