2016-2017 CT S03E07（B 签到,C 组合数学,D 莫队+容斥 ,E 签到 ,F 解一元二次公式 I 思维）ccsudeer-

题目链接

6.17 和队友开了一场gym  打的还可以吧，中间cf炸了会，有一个小时在划水 

B. Pen Pineapple Apple Pen

题意：现有两个字符  A  和 P，可以进行下面的两个操作得到一个字符串

1、两个基础的字符( A  、P都 是基础的字符) 组合成一个长度为2的字符串，两个基础字符其中一个一定要有P

2、两个长度相等 且  长度大于等于2的字符串 组合成一个字符串

做法：很明显只有2的幂次方才符合要求，然后就是判断有没有连续的 AA((1,2)  (3,4)  这样的连续两个位置) 有的话  无法得到 这个字符 

 #pragma GCC optimize(2) #include<bits/stdc++.h> #define ll long long #define maxn 1005 #define inf 1e9 #define pb push_back #define rep(i,a,b) for(int i=a;i<=b;i++) #define per(i,a,b) for(int i=a;i>=b;i--) using namespace std;  inline ll read() {  ll x=0,w=1; char c=getchar();  while(c<'0'||c>'9') {if(c=='-') w=-1; c=getchar();}  while(c<='9'&&c>='0') {x=(x<<1)+(x<<3)+c-'0'; c=getchar();}  return w==1?x:-x; } const int N=1e2+10; int f[N]; char s[N]; void solve() {     int n=strlen(s+1);     if(n==1) {         puts("YES");return;     }     if(n%2){         puts("NO");return;     }     int flag=0;     for(int i=1;i<=7;++i){         if(f[i]==n) flag=1;     }     if(!flag){         puts("NO");return;     }       ///printf("%dn",n);      for(int i=1;i<=n;i+=2){         //printf("%c %cn",s[i],s[i+1]);         if(s[i]=='A'&&s[i+1]=='A') {             puts("NO");return;         }     }     //puts("***");     printf("%sn","YES"); } int main() {     f[0]=1;     for(int i=1;i<=7;++i) f[i]=f[i-1]*2;     int _=read();while(_--)     {         scanf("%s",s+1);         solve();     } } 

C. Stickmen

题意：给你n个点m条边的图，问图中能构成下面图形的方案数：

做法：枚举边，然后用组合数学C(u,3)*C(v,2)+C(u,2)*C(v,3) 但是这里会有重复的点  被u、v共用,其实也简单，将共用的点单独拿出来，重新组合数学就好了 假设 p是重复的点

公式：

C(u,i)*C(p,3-i)*C(p-i+v,2)

C(u,i)*C(p,2-i)*C(p-i+v,3)

 #pragma GCC optimize(2) #include<bits/stdc++.h> #define ll long long #define maxn 1005 #define inf 1e9 #define pb push_back #define rep(i,a,b) for(int i=a;i<=b;i++) #define per(i,a,b) for(int i=a;i>=b;i--) using namespace std; const ll mod=1e9+7; inline ll read() {     ll x=0,w=1; char c=getchar();     while(c<'0'||c>'9') {if(c=='-') w=-1; c=getchar();}     while(c<='9'&&c>='0') {x=(x<<1)+(x<<3)+c-'0'; c=getchar();}     return w==1?x:-x; } const int N=2e2+10; vector<int>G[N]; int sz[N*N],u[N*N],v[N*N]; int n,m; ll C[N][N],ans; ll get(int n,int m) {     if(m>n) return 0;     return C[n][m]; } void add(ll &x,ll y) {     x=(x+y)%mod; } void init() {     C[0][0]=1;     for(int i=1;i<N;++i) C[i][0]=C[i][i]=1;     for(int i=2;i<N;++i){         for(int j=1;j<i;++j) C[i][j]=(C[i-1][j]+C[i-1][j-1])%mod;     } } void solve() {     for(int i=1;i<=m;++i){         set<int>st;         for(int va:G[u[i]]) st.insert(va);         for(int va:G[v[i]]) st.insert(va);           int s2=sz[u[i]]+sz[v[i]]-st.size();//重复的点           int s1=sz[u[i]]-s2-1;         int s3=sz[v[i]]-s2-1;         //printf("u:%d v:%dn",u[i],v[i]);         //printf("s1:%d s2:%d s3:%dn",s1,s2,s3);          for(int j=0;j<=min(s2,3);++j){                         add(ans,get(s1,3-j)*get(s2,j)%mod*get(s3+s2-j,2)%mod);         }         for(int j=0;j<=min(s2,2);++j){                         add(ans,get(s1,2-j)*get(s2,j)%mod*get(s3+s2-j,3)%mod);         }        } } int main() {     //puts("***");      init();     n=read(),m=read();     for(int i=1;i<=m;++i){         u[i]=read(),v[i]=read();         sz[u[i]]++,sz[v[i]]++;         G[u[i]].push_back(v[i]);         G[v[i]].push_back(u[i]);     }     solve();     printf("%lldn",ans); } /* 7 6 1 2 2 3 2 4 2 5 5 6 5 7 */

D. Strange Queries

题意：给你n(1<=n<=50000)个数，q次查询 给两个区间 (l1,r1) (l2,r2)    求所有k   区间内 (l1,r1) k的数量乘上 (l2,r2)k的数量之和

做法：直接暴力肯定超时，考虑离线处理，然后莫队搞一搞。这里还要考虑容斥一下：

(r1,r2)代表从区间 1~r1   与区间 1~r2 的权值和。

那么每次查询的两个区间就等于(r1,r2)-(r1,l2-1)-(r2,l1-1)+(l1-1,l2-1)

对这四个区间分别套用莫队即可。

 #pragma GCC optimize(2) #include<bits/stdc++.h> #define ll long long #define maxn 1005 #define inf 1e9 #define pb push_back #define rep(i,a,b) for(int i=a;i<=b;i++) #define per(i,a,b) for(int i=a;i>=b;i--) using namespace std;  inline ll read() {  ll x=0,w=1; char c=getchar();  while(c<'0'||c>'9') {if(c=='-') w=-1; c=getchar();}  while(c<='9'&&c>='0') {x=(x<<1)+(x<<3)+c-'0'; c=getchar();}  return w==1?x:-x; } const int N=5e4+10; int a[N],n,len; ll vs1[N],vs2[N]; ll ans1[N],ans2[N],ans3[N],ans4[N]; int block; struct node {     int l,r,id;     bool operator<(const node&t)const     {         if(l/block==t.l/block)         return r<t.r;         return l/block<t.l/block;     }  }c1[N],c2[N],c3[N],c4[N]; void run(node c[N],ll ans[]) {     memset(vs1,0,sizeof(vs1));     memset(vs2,0,sizeof(vs2));     int p=c[1].l,q=c[1].r;      ll now=0;     for(int i=1;i<=p;++i){         vs1[a[i]]++;     }      for(int i=1;i<=q;++i){         vs2[a[i]]++;         now+=vs1[a[i]];     }      //for(int i=1;i<=len;++i) printf("id:%d l:%d r:%dn",c[i].id,c[i].l,c[i].r);      ans[c[1].id]=now;     for(int i=2;i<=len;++i){         //printf("i:%d p:%d q:%dn",i,p,q);          for(int j=p+1;j<=c[i].l;++j) now+=vs2[a[j]],vs1[a[j]]++;         for(int j=p;j>c[i].l;--j) now-=vs2[a[j]],vs1[a[j]]--;          for(int j=q+1;j<=c[i].r;++j) now+=vs1[a[j]],vs2[a[j]]++;         for(int j=q;j>c[i].r;--j) now-=vs1[a[j]],vs2[a[j]]--;         ans[c[i].id]=now;         p=c[i].l,q=c[i].r;     }     } int main() {     n=read();     rep(i,1,n) a[i]=read();     len=read();     rep(i,1,len)     {         int l1=read(),r1=read(),l2=read(),r2=read();         c1[i]={r1,r2,i};         c2[i]={r1,l2-1,i};         c3[i]={l1-1,r2,i};         c4[i]={l1-1,l2-1,i};     }     block=sqrt(len);     sort(c1+1,c1+1+len);     sort(c2+1,c2+1+len);     sort(c3+1,c3+1+len);     sort(c4+1,c4+1+len);      run(c1,ans1);     run(c2,ans2);     run(c3,ans3);     run(c4,ans4);      for(int i=1;i<=len;++i){         ans1[i]=ans1[i]-ans2[i]-ans3[i]+ans4[i];         printf("%lldn",ans1[i]);     } } 

E. Bravebeart

题意：n（1<=n<=42）个骑士的权值w[i]   以及马的权值h[i]   一骑士一马构成一个单位 总权值为骑士的权值*马的权值。

主人公是w[1] 问如何分配使得主人公的权值严格大于其他单位的权值。

做法：很明显最大的马给主人公，其实就最大值配最小值 。签到题。

 #include<bits/stdc++.h> using namespace std; const int N=1e2+10; int n,w[N],h[N]; bool cmp(int x,int y) {  return x>y; } int main() {  int _;  scanf("%d",&_);  while(_--)  {   scanf("%d",&n);   for(int i=1;i<=n;++i) scanf("%d",&w[i]);   for(int i=1;i<=n;++i) scanf("%d",&h[i]);         sort(w+2,w+n+1);   sort(h+1,h+1+n,cmp);       int flag=1;   for(int i=2;i<=n;++i){    if(w[1]*h[1]<=w[i]*h[i]) flag=0;   }   printf("%sn",flag?"YES":"NO");     } }

F. GukiZ Height

题意和做法参考来自：博客

 

 #include<bits/stdc++.h> using namespace std; #define N 100005 #define ll long long #define ld long double using namespace std; ll n,h,a,s[N],ans=1ll<<60; int main() {  scanf("%lld%lld",&n,&h);  for(int i=0;i<n;i++){scanf("%lld",&a);s[i+1]=s[i]+a;}      for(ll i=1;i<=n;i++){   if(h-i*(i+1)/2<=s[i]){             ans=i;break;   }else{    ld a=n*n,b=(ld)2*i*n+n+2*s[n],c=(ld)i*i+i-2*h+2*s[i];    ans=min(ans,(ll)ceil((-b+sqrtl(b*b-a*c*4))/(a*2))*n+i);   }  }  printf("%lldn",ans);  return 0; } 

I. Prime Moving

题意：给你两个素数a、b  现每次只能对a加一个素数或者减一个素数，期间a一定保持为素数，问是否有最少操作次数使得能到达b，有的话  输出路径。

做法：不会，参考队友的代码。

因为奇数+奇数=偶数  

如果a为2  判断a能否一步到达b   

不能 则判断能否 先到达a+b  再到b

 

a不为2  因为奇数+奇数=偶数  的原因，a只能对a+2  a-2  和b-2  b+2 进行判断操作。

特判b==a+4 两步即可。

如果a-2是素数  b-2也是素数   a->2->b

如果a-2是素数  b+2也是素数   a->2->b+2->b

 

如果a+2是素数  b-2 也是素数 a->a+2->2->b

如果a+2是素数  b+2 也是素数a->a+2->2->b+2->b

 #include<bits/stdc++.h> using namespace std; typedef long long ll; #define IO ios::sync_with_stdio(false) #define pb push_back #define mk make_pair const int N = 1e5+10; const int mod = 1e9+7;    ll a, b;  const long long S=20; ll mult_mod(ll a,ll b,ll mod)//快速乘 {  ll res=0;  for(;b;b>>=1){   if(b&1) res=(res+a)%mod;   a=(a+a)%mod;  }  return res; } ll pow_mod(ll a,ll b,ll mod)//快速幂 {  ll res=1;  a%=mod;  for(;b;b>>=1){   if(b&1) res=mult_mod(res,a,mod);   a=mult_mod(a,a,mod);  }  return res; } int check(ll a,ll n,ll x,ll t){     ll ret=pow_mod(a,x,n);     ll last=ret;     for(ll i=1;i<=t;i++){         ret=mult_mod(ret,ret,n);         if(ret==1&&last!=1&&last!=n-1) return 1;         last=ret;     }     if(ret!=1) return 1;     return 0; } int isprime(ll n){     if(n<2)return 0;     if(n==2)return 1;     if((n&1)==0) return 0;     ll x=n-1;     ll t=0;     while((x&1)==0){x>>=1;t++;}     for(ll i=0;i<S;i++){         ll a=rand()%(n-1)+1;         if(check(a,n,x,t))             return 0;     }     return 1; }  int main(){  scanf("%lld%lld", &a, &b);  if(a == 2){   if(isprime(b-a)) printf("%lld->%lldn", a, b);   else if(isprime(b+a)){    printf("%lld->%lld->%lldn", a, b+a, b);   }   else printf("Unlucky Bennyn");  }  else{   if(isprime(b-a)) printf("%lld->%lldn", a, b); // 1步   else{    if(b == a+4 && isprime(a+2)){ // 2步     printf("%lld->%lld->%lldn", a, a+2, b);     return 0;    }    if(isprime(a-2)){     if(isprime(b-2)){ // 2步      printf("%lld->%lld->%lldn", a, 2ll, b);      return 0;     }     else if(isprime(b+2)){ // 3步      printf("%lld->%lld->%lld->%lldn", a, 2ll, b+2, b);      return 0;     }    }    if(isprime(a+2)){     if(isprime(b-2)){      printf("%lld->%lld->%lld->%lldn", a, a+2, 2ll, b);      return 0;     }     else if(isprime(b+2)){      printf("%lld->%lld->%lld->%lld->%lldn", a, a+2, 2ll, b+2, b);      return 0;     }    }    printf("Unlucky Bennyn");   }  }  return 0; }