csp-s模拟9697题解

题面：https://www.cnblogs.com/Juve/articles/11790223.html

96：

刚一看以为是水题，直接等差数列求和就好了，然后发现模数不是质数，还要1e18*1e18，就弃了，看T3，然后看错题了，打了个dij的40分暴力

然后看T1发现我好像会一个叫做慢速乘的东西（颓AlpaCa博客颓到的，现在应该是我的模板的第二个），然后就不用打高精了，

至于模数不是质数，因为答案一定是整数，而我的式子最终要除以4，所以就在乘之前先让它除，然后乘，然后T1就A了，

T2打了个n方暴力，骗到75，rk6还是近几次最好？可能是我太垃圾了。。。

T1：

上面都说过了，不再细说

 #include<iostream>

 #include<cstdio>

 #include<cstring>

 #include<algorithm>

 #define int long long

 using namespace std;

 int x,y,xx,yy,tot=;

 int ans=,mod;

 int mul(int a,int b,int p){

     int res=;

     while(b){

         if(b&) res=(res+a)%p;

         a=(a+a)%p;

         b>>=;

     }

     return res;

 }

 signed main(){

     freopen("sum.in","r",stdin);

     freopen("sum.out","w",stdout);

     scanf("%lld%lld%lld%lld%lld",&x,&y,&xx,&yy,&mod);

     int p=(x+y-),q=(x+yy-),pp=(xx+y-),qq=(xx+yy-);

     int xkl1=(p+q+pp+qq),xkl2=(yy-y+),xkl3=(xx-x+);

     while(tot<&&xkl1%==){

         xkl1/=;

         ++tot;

     }

     while(tot<&&xkl2%==){

         xkl2/=;

         ++tot;

     }

     while(tot<&&xkl3%==){

         xkl3/=;

         ++tot;

     }

     ans=mul(mul(xkl2,xkl3,mod)%mod,xkl1,mod)%mod;

     printf("%lld\n",ans);

     return ;

 }

T2：

就贪心地扫，二分最大不可行的位置，然而n²logn²复杂度不够优秀，我们倍增缩小二分的区间

 #include<iostream>

 #include<cstdio>

 #include<cstring>

 #include<algorithm>

 #include<vector>

 #define int long long

 #define re register

 using namespace std;

 inline int read(){

     re int x=;re char ch=getchar();

     while(ch<''||ch>'') ch=getchar();

     while(ch>=''&&ch<=''){

         x=(x<<)+(x<<)+ch-'';

         ch=getchar();

     }

     return x;

 }

 const int MAXN=1e6+;

 int n,m,a[MAXN],b[MAXN],ans=;

 int staa[MAXN],stab[MAXN],topa,topb;

 bool check(int l,int r){

     topa=topb=;

     for(int i=l;i<=r;++i) staa[++topa]=a[i],stab[++topb]=b[i];

     sort(staa+,staa+topa+),sort(stab+,stab+topb+);

     int tot=;

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

         tot+=staa[i]*stab[i];

         if(tot>m) return ;

     }

     return ;

 }

 int get(int pos){

     int poss=;

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

         poss=i;

         if(pos+(<<i)->n) break;

         if(!check(pos,pos+(<<i)-)){

             poss=i;

             break;

         }

     }

     int l=pos+(<<(poss-))-,r=pos+(<<poss)-;

     int res=l;

     while(l<=r){

         int mid=(l+r)>>;

         if(check(pos,mid)) res=max(res,mid),l=mid+;

         else r=mid-;

     }

     return res+;

 }

 signed main(){

     freopen("pair.in","r",stdin);

     freopen("pair.out","w",stdout);

     n=read(),m=read();

     for(re int i=;i<=n;++i) a[i]=read();

     for(re int i=;i<=n;++i) b[i]=read();

     for(re int i=;i<=n;){

         i=get(i);

         ++ans;

     }

     printf("%lld\n",ans);

     return ;

 }

T3：

不太会

97：

T1发现了50分性质就跑了，T2感觉是个sb的dp，但是由于我设的状态，导致他有8个转移，复杂度也只能过70分，T3玄学原因10分暴力都挂了

dp要再复习，dp渣有什么好说的？

发下题解发现我不懂T1的解释，T2又太水了，导致没什么可讲的

 #include<iostream>

 #include<cstdio>

 #include<cstring>

 #include<algorithm>

 #define int long long

 using namespace std;

 const int MAXN=1e5+,mod=1e9+;

 int n,a[MAXN],cnt=,ans=,tong[MAXN];

 int q_pow(int a,int b,int p){

     int res=;

     while(b){

         if(b&) res=res*a%p;

         a=a*a%p;

         b>>=;

     }

     return res;

 }

 signed main(){

     freopen("game.in","r",stdin);

     freopen("game.out","w",stdout);

     scanf("%lld",&n);

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

         scanf("%lld",&a[i]);

         ++tong[a[i]];

         cnt+=(a[i]==-);

     }

     ans=(q_pow(,n-,mod)-+mod)%mod;

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

         ans=(ans-q_pow(,tong[i],mod)++mod)%mod;

     }

     printf("%lld\n",ans);

     return ;

 }

T2：

 #include<iostream>

 #include<cstdio>

 #include<cstring>

 #include<algorithm>

 #define int long long

 #define re register

 using namespace std;

 const int mod=1e9+;

 int t,n,s,f[][];

 signed main(){

     freopen("flower.in","r",stdin);

     freopen("flower.out","w",stdout);

     scanf("%lld",&t);

     while(t--){

         scanf("%lld%lld",&n,&s);

         f[][]=f[][]=s;

         f[][]=s*s%mod;

         f[][]=(s*s%mod*s%mod-s+mod)%mod;

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

             f[i][]=(f[i-][]*(s-)%mod+f[i-][]*(s-)%mod)%mod;

             f[i][]=(f[i-][]*(s-)%mod+f[i-][]*(s-)%mod+f[i-][]*(s-)%mod)%mod;

         }

         printf("%lld\n",f[n][]%mod);

     }

     return ;

 }

T3：

不会，DEE树钛锯蜡

98：

全程划水，然后T130分暴力又挂了，因为限制的循环层数太小，导致没跑出来

T2一个错误的状压dp水了35分

好吧我现在只会T2

设定01状态，预处理出每个点i，点亮它j秒后那些灯状态会取反，然后倒着转移

话说Yu-shi给我讲的时候我一直理解成正序还说服了自己，我真是太bang了

 #include<iostream>

 #include<cstdio>

 #include<cstring>

 #include<algorithm>

 using namespace std;

 int n,fa[],zt[],s,dp[][],ans=0x3f3f3f3f;

 bool f[][(<<)+];

 int calc(int state){

     int res=;

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

         if(state&(<<(i-))){

             res^=(<<(fa[i]-));

         }

     }

     return res;

 }

 void print(int sta){

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

         if(sta&(<<(i-))) cout<<;

         else cout<<;

     }

     cout<<' ';

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

         if(sta&(<<(i-))) cout<<;

         else cout<<;

     }

     cout<<' ';

 }

 int main(){

     freopen("decoration.in","r",stdin);

     freopen("decoration.out","w",stdout);

     scanf("%d",&n);

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

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

         scanf("%d",&zt[i]);

         s|=(zt[i]<<(i-));

         int p=i;

         dp[i][]=<<(i-);

         p=fa[p];

         for(int j=;j<=n;++j,p=fa[p]){

             if(p!=) dp[i][j]=dp[i][j-]|(<<(p-));

             else dp[i][j]=dp[i][j-];

         }

     }

     f[][]=;

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

         for(int s=;s<(<<n);++s){

             f[i][s]|=f[i-][s];

             for(int j=;j<=n;++j){

                 f[i][s^dp[j][i]]|=f[i-][s];

             }

         }

     }

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

         if(f[i][s]){

             ans=i;

             break;

         }

     }

     printf("%d\n",ans);

     return ;

 }

巴特西

csp-s模拟9697题解

最新文章

热门文章