2017 多校联合训练 8 题解

Problem 1001

Problem 1002

如果不考虑必须互质的条件

那么可以通过递归求出所有的数

现在考虑必须互质

先用筛法预处理出每个数的质因数

由于每个数的质因数不会很多

所以直接容斥原理即可

  1 #include<iostream>
  2 #include<cstdio>
  3 #include<cmath>
  4 #include<cstdlib>
  5 #include<algorithm>
  6 #include<cstring>
  7 #include<string>
  8 #include<vector>
  9 #include<map>
 10 #include<set>
 11 #include<queue>
 12 #include<ctime>
 13 using namespace std;
 14 const int mod=1e9+7;
 15 struct ss
 16 {
 17     int x,id;
 18 };
 19 struct data
 20 {
 21     int to,nxt;
 22 };
 23 data e[3000010];
 24 int head[1000010];
 25 int n,cnt,QaQ=1;
 26 ss a[10010];
 27 int ans[1000010],g[1000010],f[1000010],c[1000010],ct=0;
 28 //vector<int> vc[1000010];
 29 inline bool cmp(ss a,ss b)
 30 {
 31     return a.x<b.x;
 32 }
 33 void add(int x,int y)
 34 {
 35     e[QaQ].to=y;
 36     e[QaQ].nxt=head[x];
 37     head[x]=QaQ++;
 38 }
 39 void init()
 40 {
 41     int i,j;
 42     for (i=2;i<=1000000;i++)
 43     {
 44         if (g[i]) continue;
 45         c[++ct]=i;
 46         for (j=i+i;j<=1000000;j+=i)
 47             g[j]=1;
 48     }
 49     memset(g,0,sizeof(g));
 50     memset(head,-1,sizeof(head));
 51     for (i=1;i<=ct;i++)
 52         for (j=c[i];j<=1000000;j+=c[i])
 53             add(j,c[i]);
 54     memset(c,0,sizeof(c));
 55     for (i=1;i<=1000000;i++)
 56         for (j=i;j<=1000000;j+=i)
 57             g[j]++;
 58     for (i=1;i<=1000000;i++)
 59         c[i]=(c[i-1]+g[i])%mod;
 60     for (i=1;i<=1000000;i++)
 61         f[i]=(c[i]+i-g[i]+mod)%mod;    
 62 }
 63 int cal(int x)
 64 {
 65     if (x==0) return 0;
 66     return (f[x]-1+mod)%mod;
 67 }
 68 int dfs(int lim,int t,int u,int fg)
 69 {
 70     if (t>lim) return 0;
 71     int ret=fg*cal(lim/t);
 72     int i;
 73     for (i=u+1;i<=cnt;i++)
 74         (ret+=dfs(lim,t*g[i],i,-fg)+mod)%=mod;
 75     return ret;
 76 }
 77 int calc(int x)
 78 {
 79     if (x==1) return 1;
 80     cnt=0;
 81     //for (auto u:vc[x])
 82     for (int i=head[x];~i;i=e[i].nxt)
 83         g[++cnt]=e[i].to;
 84     if (cnt==1&&g[1]==x)
 85         return cal(x);
 86     return dfs(x,1,0,1);
 87 }
 88 int main()
 89 {
 90     int tt=0;
 91     init();
 92     //cout<<sizeof(vc)<<endl;
 93     //double t=clock();
 94     while (~scanf("%d",&n))
 95     {
 96         tt++;
 97         a[tt].id=tt;
 98         a[tt].x=n;
 99     }
100     sort(a+1,a+tt+1,cmp);
101     int pre=0,sum=0;
102     int i,j;
103     //for (i=1;i<=10;i++)
104     //    cout<<i<<" "<<f[i]<<endl;
105     for (i=1;i<=tt;i++)
106     {
107         for (j=pre+1;j<=a[i].x;j++)
108             (sum+=calc(j))%=mod;;
109         ans[a[i].id]=sum;
110         pre=a[i].x;
111     }
112     for (i=1;i<=tt;i++)
113         printf("%d
",ans[i]);
114     //t=clock()-t;
115     //cout<<t/1000<<endl;
116     return 0;
117 }

View Code

Problem 1003

Problem 1004

Problem 1005

Problem 1006

比赛的时候没有想到可以直接用AC自动机暴力过去

先用AC自动机求出第一个串包含哪些单词

然后直接用find求哪些单词在第二个串中也有

  1 #include<iostream>
  2 #include<cstdio>
  3 #include<cmath>
  4 #include<cstdlib>
  5 #include<algorithm>
  6 #include<cstring>
  7 #include<string>
  8 #include<vector>
  9 #include<map>
 10 #include<set>
 11 #include<queue>
 12 using namespace std;
 13 vector<string> vc;
 14 struct ACa{
 15     int next[110000][128],fail[120000];
 16     string end[120000];
 17     int root,len;
 18     int newnode(){
 19         for(int i=0;i<128;i++)
 20             next[len][i]=-1;
 21         end[len]="";
 22         len++;
 23         return len-1;
 24     }
 25     void clear(){
 26         len=0;
 27         root=newnode();
 28         return;
 29     }
 30     void insert(char s[],int num){
 31         int ls=strlen(s);
 32         int now=root;
 33         string t="";
 34         for(int i=0;i<ls;i++){
 35             if(next[now][s[i]]==-1)
 36                 next[now][s[i]]=newnode();
 37             now=next[now][s[i]];
 38             t+=s[i];
 39             end[now]=t;    
 40         }
 41     }
 42     void build(){
 43         queue<int>q;
 44         int i;
 45         fail[root]=root;
 46         for(i=0;i<128;i++){
 47             if(next[root][i]==-1)
 48                 next[root][i]=root;
 49             else{
 50                 fail[next[root][i]]=root;
 51                 q.push(next[root][i]);
 52             }
 53         }
 54         while(!q.empty()){
 55             int now=q.front();
 56             q.pop();
 57             for(i=0;i<128;i++){
 58                 if(next[now][i]==-1)
 59                     next[now][i]=next[fail[now]][i];
 60                 else{
 61                     fail[next[now][i]]=next[fail[now]][i];
 62                     q.push(next[now][i]);
 63                 }
 64             }
 65         }
 66         return;
 67     }
 68     bool vis[600];
 69     void ask(char c[],int n,int num){
 70         bool flag1=false;
 71         memset(vis,false,sizeof(vis));
 72         int lc=strlen(c);
 73         int now=root;
 74         int i;
 75         for(i=0;i<lc;i++){
 76             now=next[now][c[i]];
 77             int temp=now;
 78             while(temp!=root){
 79                 flag1=1;
 80                 vc.push_back(end[temp]);
 81                 temp=fail[temp];
 82             }
 83         }
 84     }
 85 };
 86 ACa ac;
 87 char c[100010];
 88 string s[100010];
 89 int m,n;
 90 int main()
 91 {
 92     int _;
 93     scanf("%d",&_);
 94     while (_--)
 95     {
 96         scanf("%d",&n);
 97         int i;
 98         ac.clear();
 99         for (i=1;i<=n;i++)
100         {
101             scanf("%s",c);
102             s[i].assign(c);
103             ac.insert(c,i);
104         }
105         ac.build();
106         scanf("%d",&m);
107         for (i=1;i<=m;i++)
108         {
109             int x,y;
110             scanf("%d%d",&x,&y);
111             strcpy(c,s[x].c_str());
112             vc.clear();
113             ac.ask(c,n,i);
114             int mx=0;
115             for (auto u:vc)
116                 if (~s[y].find(u))
117                     mx=max(mx,(int)u.size());
118             printf("%d
",mx);
119         }
120     }
121     return 0;
122 }

View Code

Problem 1007

Problem 1008

哇，比赛的时候我没看到前面那个条件。

激动地直接上了bitset。

然后T回来了

后来czy说这是NP-Hard问题，肯定有附加条件的，一看果然

他的这个条件保证了能组合出的数的取值范围一定是连续的。

然后就很简单了

#include <bits/stdc++.h>

using namespace std;

#define rep(i, a, b)	for (int i(a); i <= (b); ++i)
#define dec(i, a, b)	for (int i(a); i >= (b); --i)
#define MP		make_pair
#define fi		first
#define se		second


typedef long long LL;

const int N = 1e3 + 10;
int n, k;
int x, y;
int a[N];
int T;
char ch;


int main(){

	scanf("%d", &T);
	while (T--){
		scanf("%d%d", &n, &k);
		rep(i, 1, n) scanf("%d", a + i);
		getchar();
		x = y = 0;
		rep(i, 1, n){
			scanf("%c ", &ch);
			if (ch == 'N') x -= a[i], y += a[i];
			else if (ch == 'D') x -= a[i];
			else if (ch == 'L') y += a[i];
		}

		if (k >= x && k <= y) puts("yes");
		else puts("no");
	}


	return 0;
}

Problem 1011

直接用容斥原理进行计数即可

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 const int inf=(1<<30)-1;
 4 const int N=2010;
 5 #define REP(i,n) for(int i=(0);i<(n);i++)
 6 #define FOR(i,j,n) for(int i=(j);i<=(n);i++)
 7 typedef long long ll;
 8 typedef pair<int,int> PII;
 9 int IN(){
10     int c,f,x;
11     while (!isdigit(c=getchar())&&c!='-');c=='-'?(f=1,x=0):(f=0,x=c-'0');
12     while (isdigit(c=getchar())) x=(x<<1)+(x<<3)+c-'0';return !f?x:-x;
13 }
14 #define de(x) cout << #x << "=" << x << endl
15 #define MP make_pair
16 #define PB push_back
17 #define fi first
18 #define se second
19 int T;
20 int fac[N],inv[N];    
21 const int p=1e9+7;
22 ll dp[2010][2010];
23 int Pow(int x,int y)
24 {
25     int ans=1;
26     while(y)
27     {
28         if(y&1) ans=1ll*ans*x%p;
29         x=1ll*x*x%p;
30         y>>=1;
31     }
32     return ans;
33 }
34 void init()
35 {
36     fac[0]=1;
37     FOR(i,1,N) fac[i]=1ll*fac[i-1]*i%p;
38     inv[N-1]=Pow(fac[N-1],p-2);
39     for (int i=N-1;i;i--) inv[i-1]=1ll*inv[i]*i%p;
40     dp[0][0]=1;
41     for(int i=1;i<N;i++)
42     for(int j=1;j<N;j++)
43     {
44         dp[i][j]=(dp[i-1][j]*j+dp[i-1][j-1])%p;
45     }
46 }
47 int n,m;
48 int A(int x,int y)
49 {
50     return 1ll*fac[x]*inv[x-y]%p;
51 }
52 int main()
53 {
54     init();
55     scanf("%d",&T);
56     while(T--)
57     {
58         scanf("%d%d",&n,&m);
59         ll ans=0;
60         for(int i=2;i<=m;i++)
61         for(int j=1;j<i;j++)
62         {
63             ans=(ans+1ll*dp[n][j]*dp[n][i-j]%p*A(m,i)%p)%p;
64         }
65         printf("%lld
",ans);
66     }
67     return 0;
68 }

View Code