佳木斯集训Day3

D3是我的巅峰

D3的出题人毒瘤！！！T3放了一道莫队，我们全体爆炸，到现在只有一个奆老A掉了T3

据说lkh被晓姐姐D了

T1是个26进制数，当时在考场上想了好久才想到（太次了）注意需要处理一下溢出的情况，不过幸好最后还是A了

 #include <bits/stdc++.h>

 #define MAXN 200050

 using namespace std;

 int n,point,start,finish,x=;

 struct Node{

     int num;

     int cha;

 }h[MAXN];

 char a[MAXN],b[MAXN];

 int c[MAXN];

 int ans[MAXN];

 int main()

 {

     char qq;

     cin>>n;

     for(int i=;i<=n;i++)

     {

         cin>>qq;

         a[i]=qq-'a';

     }

     for(int i=;i<=n;i++)

     {

         cin>>qq;

         b[i]=qq-'a';

     }

     for(int i=n;i>=;i--)

     {

         if(ans[i]+a[i]+b[i]>=)

         {

             ans[i]=ans[i]+a[i]+b[i]-;

             ans[i-]++;

         }

         else

         ans[i]=ans[i]+a[i]+b[i];

     }

     for(int i=;i<=n;i++)

     {

         int l;

         l=ans[i];

         ans[i]=ans[i]/+x;

         if(l%==)

         x=;

         else x=;

     }

     for(int i=;i<=n;i++)

     cout<<char(ans[i]+'a');

 }

T2我写的大暴力，然后TLE20，最后正解是逆元和欧拉函数？？？

 #include<bits/stdc++.h>

 using namespace std;

 const int sz=3e5+;

 const int mod=1e8+;

 int n,x;

 int inv[sz],a[sz],b[sz];

 int cnt[sz],f[sz];

 void init(){

     a[]=b[]=;

     inv[]=a[]=b[]=;

     for(int i=;i<sz;i++){

         inv[i]=1ll*(mod-mod/i)*inv[mod%i]%mod;

         a[i]=1ll*a[i-]*i%mod;

         b[i]=1ll*b[i-]*inv[i]%mod;

     }

 }

 int C(int n,int m){

     if(!n) return ;

     return 1ll*a[n]*b[m]%mod*b[n-m]%mod;

 }

 bool cur(int len){

     for(int i=sz-;i>=;i--){

         f[i]=C(cnt[i],len);

         for(int j=;i*j<sz;j++) f[i]=(f[i]-f[i*j]+mod)%mod;

     }

     return f[];

 }

 int main(){

     init();

     scanf("%d",&n);

     for(int i=;i<=n;i++) scanf("%d",&x),cnt[x]++;

     for(int i=;i<sz;i++) for(int j=;i*j<sz;j++) cnt[i]+=cnt[i*j];

     x=;

     while(!cur(x)&x<=) x++;

     if(x<=) printf("%d",x);

     else printf("-1");

 }

T3的莫队我也写的暴力（暴力大法好），也是TLE20，正解莫队，实在不会，这个坑先暂时放这里23333

代码嘛...奉上20分的把

 #include <bits/stdc++.h>

 #define MAXN 100050

 using namespace std;

 struct Node{

     int one;

     int two;

 }c[MAXN];

 int a[MAXN],sum1[MAXN],sum2[MAXN],t[MAXN],q,k,n,l,r;

 int lowbit(int x)

 {

     return x&(-x);

 }

 int update(int x,int y,int t)

 {

     for(int i=;i<=1e5;i=i+lowbit(x))

     {

         if(t==)

         c[i].one=c[i].one+y;

         else

         c[i].two=c[i].two+y;

     }

 }

 int query(int x,int t)

 {

     int ans=;

     if(t==)

     {

         for(int i=x;i>;i=i-lowbit(x))

     {

         ans+=c[i].one;

     }

     return ans;

     }

     else

     {

         for(int i=x;i>;i=i-lowbit(x))

     {

         ans+=c[i].two;

     }

     return ans;

     }

 }

 int main()

 {

     cin>>n>>k;

     for(int i=;i<=n;i++)

     {

         cin>>t[i];

     }

     for(int i=;i<=n;i++)

     cin>>a[i];

     cin>>q;

     while(q--)

     {

         int ans=;

         cin>>l>>r;

         for(int i=l;i<=r;i++)

         {

             int a1=,a2=,sum=;

             for(int j=i;j<=r;j++)

             {

                 if(t[j]==)

                 a1+=a[j];

                 else a2+=a[j];

                 if(a1-a2==k)

                 sum++;

             }ans+=sum;

         }

         cout<<ans<<endl;

     }

 }

巴特西

佳木斯集训Day3

最新文章

热门文章