您的位置: 首页  >  IT文章  >  csp-s模拟9697题解

csp-s模拟9697题解

分类: IT文章 • 2025-01-23 08:16:01

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

96：

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

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

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

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

T1：

上面都说过了，不再细说

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 #include<algorithm>
 5 #define int long long
 6 using namespace std;
 7 int x,y,xx,yy,tot=0;
 8 int ans=0,mod;
 9 int mul(int a,int b,int p){
10     int res=0;
11     while(b){
12         if(b&1) res=(res+a)%p;
13         a=(a+a)%p;
14         b>>=1;
15     }
16     return res;
17 }
18 signed main(){
19     freopen("sum.in","r",stdin);
20     freopen("sum.out","w",stdout);
21     scanf("%lld%lld%lld%lld%lld",&x,&y,&xx,&yy,&mod);
22     int p=(x+y-1),q=(x+yy-1),pp=(xx+y-1),qq=(xx+yy-1);
23     int xkl1=(p+q+pp+qq),xkl2=(yy-y+1),xkl3=(xx-x+1);
24     while(tot<2&&xkl1%2==0){
25         xkl1/=2;
26         ++tot;
27     }
28     while(tot<2&&xkl2%2==0){
29         xkl2/=2;
30         ++tot;
31     }
32     while(tot<2&&xkl3%2==0){
33         xkl3/=2;
34         ++tot;
35     }
36     ans=mul(mul(xkl2,xkl3,mod)%mod,xkl1,mod)%mod;
37     printf("%lld
",ans);
38     return 0;
39 }
View Code

T2：

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

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 #include<algorithm>
 5 #include<vector>
 6 #define int long long
 7 #define re register
 8 using namespace std;
 9 inline int read(){
10     re int x=0;re char ch=getchar();
11     while(ch<'0'||ch>'9') ch=getchar();
12     while(ch>='0'&&ch<='9'){
13         x=(x<<3)+(x<<1)+ch-'0';
14         ch=getchar();
15     }
16     return x;
17 }
18 const int MAXN=1e6+5;
19 int n,m,a[MAXN],b[MAXN],ans=0;
20 int staa[MAXN],stab[MAXN],topa,topb;
21 bool check(int l,int r){
22     topa=topb=0;
23     for(int i=l;i<=r;++i) staa[++topa]=a[i],stab[++topb]=b[i];
24     sort(staa+1,staa+topa+1),sort(stab+1,stab+topb+1);
25     int tot=0;
26     for(int i=1;i<=topa;++i){
27         tot+=staa[i]*stab[i];
28         if(tot>m) return 0;
29     }
30     return 1;
31 }
32 int get(int pos){
33     int poss=1;
34     for(int i=1;;++i){
35         poss=i;
36         if(pos+(1<<i)-1>n) break;
37         if(!check(pos,pos+(1<<i)-1)){
38             poss=i;
39             break;
40         }
41     }
42     int l=pos+(1<<(poss-1))-1,r=pos+(1<<poss)-1;
43     int res=l;
44     while(l<=r){
45         int mid=(l+r)>>1;
46         if(check(pos,mid)) res=max(res,mid),l=mid+1;
47         else r=mid-1;
48     }
49     return res+1;
50 }
51 signed main(){
52     freopen("pair.in","r",stdin);
53     freopen("pair.out","w",stdout);
54     n=read(),m=read();
55     for(re int i=1;i<=n;++i) a[i]=read();
56     for(re int i=1;i<=n;++i) b[i]=read();
57     for(re int i=1;i<=n;){
58         i=get(i);
59         ++ans;
60     }
61     printf("%lld
",ans);
62     return 0;
63 }
View Code

T3：

不太会

97：

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

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

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

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 #include<algorithm>
 5 #define int long long
 6 using namespace std;
 7 const int MAXN=1e5+5,mod=1e9+7;
 8 int n,a[MAXN],cnt=0,ans=0,tong[MAXN];
 9 int q_pow(int a,int b,int p){
10     int res=1;
11     while(b){
12         if(b&1) res=res*a%p;
13         a=a*a%p;
14         b>>=1;
15     }
16     return res;
17 }
18 signed main(){
19     freopen("game.in","r",stdin);
20     freopen("game.out","w",stdout);
21     scanf("%lld",&n);
22     for(int i=1;i<=n;++i){
23         scanf("%lld",&a[i]);
24         ++tong[a[i]];
25         cnt+=(a[i]==-1);
26     }
27     ans=(q_pow(2,n-1,mod)-1+mod)%mod;
28     for(int i=1;i<=n;++i){
29         ans=(ans-q_pow(2,tong[i],mod)+1+mod)%mod;
30     }
31     printf("%lld
",ans);
32     return 0;
33 }
View Code

T2：

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 #include<algorithm>
 5 #define int long long
 6 #define re register
 7 using namespace std;
 8 const int mod=1e9+7;
 9 int t,n,s,f[100005][2];
10 signed main(){
11     freopen("flower.in","r",stdin);
12     freopen("flower.out","w",stdout);
13     scanf("%lld",&t);
14     while(t--){
15         scanf("%lld%lld",&n,&s);
16         f[1][0]=f[3][1]=s;
17         f[2][0]=s*s%mod;
18         f[3][0]=(s*s%mod*s%mod-s+mod)%mod;
19         for(int i=4;i<=n;++i){
20             f[i][0]=(f[i-1][0]*(s-1)%mod+f[i-2][0]*(s-1)%mod)%mod;
21             f[i][1]=(f[i-1][1]*(s-1)%mod+f[i-2][1]*(s-1)%mod+f[i-3][0]*(s-1)%mod)%mod;
22         }
23         printf("%lld
",f[n][1]%mod);
24     }
25     return 0;
26 }
View Code

T3：

不会，DEE树钛锯蜡

98：

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

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

好吧我现在只会T2

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

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

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 #include<algorithm>
 5 using namespace std;
 6 int n,fa[20],zt[20],s,dp[17][17],ans=0x3f3f3f3f;
 7 bool f[17][(1<<16)+5];
 8 int calc(int state){
 9     int res=0;
10     for(int i=2;i<=n;++i){
11         if(state&(1<<(i-1))){
12             res^=(1<<(fa[i]-1));
13         }
14     }
15     return res;
16 }
17 void print(int sta){
18     for(int i=1;i<=n;++i){
19         if(sta&(1<<(i-1))) cout<<1;
20         else cout<<0;
21     }
22     cout<<' ';
23     for(int i=n;i>=1;--i){
24         if(sta&(1<<(i-1))) cout<<1;
25         else cout<<0;
26     }
27     cout<<' ';
28 }
29 int main(){
30     freopen("decoration.in","r",stdin);
31     freopen("decoration.out","w",stdout);
32     scanf("%d",&n);
33     for(int i=2;i<=n;++i) scanf("%d",&fa[i]);
34     for(int i=1;i<=n;++i){
35         scanf("%d",&zt[i]);
36         s|=(zt[i]<<(i-1));
37         int p=i;
38         dp[i][1]=1<<(i-1);
39         p=fa[p];
40         for(int j=2;j<=n;++j,p=fa[p]){
41             if(p!=0) dp[i][j]=dp[i][j-1]|(1<<(p-1));
42             else dp[i][j]=dp[i][j-1];
43         }
44     }
45     f[0][0]=1;
46     for(int i=1;i<=n;++i){
47         for(int s=0;s<(1<<n);++s){
48             f[i][s]|=f[i-1][s];
49             for(int j=1;j<=n;++j){
50                 f[i][s^dp[j][i]]|=f[i-1][s];
51             }
52         }
53     }
54     for(int i=0;i<=n;++i){
55         if(f[i][s]){
56             ans=i;
57             break;
58         }
59     }
60     printf("%d
",ans);
61     return 0;
62 }
View Code

相关推荐