牛客练习赛48

Problem A 小w的a+b问题

https://ac.nowcoder.com/acm/contest/923/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=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;
int a[N];
char str;
struct node{};
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);
    if(n==-1){
        cout<<"No solution"<<endl;
        return 0;
    }
    printf("%d %d\n",2147483647,2147483647+n+2);
    //}

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

Problem B 小w的a=b问题

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

题意：

题解：线性筛+后缀和+贪心

C++版本一

1、对两个数组桶排序；

2、求后缀和；

3、筛法求出每个数的最小非1质因子；

4、从后向前把每个数分成最小非1质因子和这个数/最小非1质因子；

5、判断每个数的数量是否相同；

/*
*@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;
ll ans,cnt,flag,temp,sum;
int a[N],b[N];
ll c[N],d[N];
int pre[N],prime[N],num[N];
char str;
struct node{};
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);
    prime[0]=prime[1]=1;
    num[0]=num[1]=1;
    for(int i=2;i<N;i++){
        if(!prime[i]){
            pre[++cnt]=i;
            num[i]=i;
        }
        for(int j=1;j<=cnt&&i*pre[j]<N;j++){
            prime[i*pre[j]]=1;
            num[i*pre[j]]=pre[j];
            if(i%pre[j]==0){
                break;
            }
        }
        //cout<<num[i]<<endl;
    }
    //cout<<cnt<<endl;
    scanf("%d",&t);
    while(t--){
        scanf("%d%d",&n,&m);
        for(int i=0;i<N;i++)c[i]=0,d[i]=0;
        for(int i=1;i<=n;i++){
            scanf("%d",&a[i]);
            c[a[i]]++;
        }
        for(int i=1;i<=m;i++){
            scanf("%d",&b[i]);
            d[b[i]]++;
        }
        for(int i=100000;i>=1;i--){
            c[i]+=c[i+1];
            d[i]+=d[i+1];
        }
        for(int i=100000;i>=2;i--){
            temp=c[i];
            c[i]=0;
            c[i/num[i]]+=temp;
            c[num[i]]+=temp;
            temp=d[i];
            d[i]=0;
            d[i/num[i]]+=temp;
            d[num[i]]+=temp;
        }
        ans=1;
        for(int i=2;i<N;i++){
            //cout<<c[i]<<" "<<d[i]<<endl;
            ans&=(c[i]==d[i]);
        }
        cout<<(ans?"equal":"unequal")<<endl;
    }

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

Problem C 小w的糖果

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

题意：

题解：数学+差分

C++版本一

1、对于类型1，直接差分；

2、对于类型2，差分每次增加的量等于当前已经操作的人数；

3、等于类型3，差分每次增加的量等于当前已经操作的人数+2*上一次类型3进行类型2的值；

/*
*@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;
ll ans[N],cnt,flag,temp,sum;
ll a[3][N];
char str;
struct node{};
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);
        memset(a,0,sizeof(a));
        for(int i=1;i<=m;i++){
            scanf("%d%d",&p,&k);
            a[p-1][k]++;
        }
        ll one=0;
        ll addone=0,add=0;
        ll timesone=0,timesadd=0,times=0;
        ll now=0;
        for(int i=1;i<=n;i++){
            one=(one+a[0][i])%MOD;
            addone=(addone+a[1][i])%MOD;
            timesone=(timesone+a[2][i])%MOD;
            add=(add+addone)%MOD;
            times=(times+2*timesadd+timesone)%MOD;
            timesadd=(timesadd+timesone)%MOD;
            now=(one+add+times)%MOD;
            printf("%lld%c",now," \n"[i==n]);
        }
    }

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

Problem D 小w的基站网络

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

题意：

题解：

C++版本一

Problem E 小w的矩阵前k大元素

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

题意：

题解：

C++版本一

Problem F 小w的互质集

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

题意：

题解：

C++版本一