模拟81考试rp爆发随机化A了T3,还有绿框框。。。。。。

完了我掉rp了

10.22update:rp没掉完,T1没想着能A,本来我是想输出样例,但是有想到反正那个式子也能正确输出样例,干脆就交了,然后它竟然A了

然而我并不知道为什么是$\frac{n^2-1}{9}$,这个AC完全是运气,还靠这个AC苟到了rk2

其实我根本配不上那个名次,偶然罢了,就是比较傻想都没想就把本来是骗分的程序交了上去

模拟81的T3也是想着骗分所以就把随机化交了上去,然后它也过了

考试老是想着骗分,不会正解就骗分,这样可不行呀。集训还有一半,要努力呀

T1:

状压dp,枚举第i行,i行状态,上一行状态,转移稍sb

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 #include<algorithm>
 5 #define re register
 6 #define int long long
 7 using namespace std;
 8 const int inf=0x7fffffff;
 9 int n,m,a[12][12],ans=inf,f[12][1<<11][1<<11];
10 int p[1<<11],val[12][1<<11],h[12];
11 bool bl[12][12];
12 char ch[12];
13 int lowbit(int x){
14     return x&(-x);
15 }
16 signed main(){
17     scanf("%lld%lld",&n,&m);
18     for(re int i=1;i<=n;++i){
19         scanf("%s",ch+1);
20         for(re int j=1;j<=m;++j)
21             bl[i][j]=ch[j]-'0';
22     }
23     for(re int i=1;i<=n;++i)
24         for(re int j=1;j<=m;++j)
25             scanf("%lld",&a[i][j]);
26     for(re int j=1;j<=m;++j) a[n+1][j]=inf;
27     for(re int i=1;i<=n;++i)
28         for(re int j=1;j<=m;++j){
29             if(!bl[i][j]) continue;
30             h[i]|=(1<<(j-1));
31         }
32     h[0]=(1<<m)-1;
33     for(re int i=1;i<=n+1;++i){
34         for(re int s=0;s<(1<<m);++s)
35             for(re int j=1;j<=m;++j)
36                 if(s&(1<<(j-1))) val[i][s]+=a[i][j];
37     }
38     for(re int i=0;i<(1<<m);++i){
39         p[i]=i;
40         for(re int j=1;j<=m;++j)
41             if(i&(1<<(j-1)))
42                 p[i]|=((1<<(j-2))|(1<<j));
43     }
44     memset(f,0x7f,sizeof(f));f[0][0][0]=0;
45     for(re int k=1;k<=n+1;++k) {
46         for(re int i=0;i<(1<<m);++i)
47             for(re int j=0;j<(1<<m);++j){
48                 re int now=(~((i|p[j]|h[k-1])&((1<<m)-1)));
49                 f[k][i][j]=min(f[k][i][j],f[k-1][j][now&((1<<m)-1)]+val[k][i]);
50             }
51         for(re int i=0;i<(1<<m);++i)
52             for(re int j(1<<m);j>=0;--j)
53                 for(re int l=j;l;l-=lowbit(l))
54                     f[k][i][j^lowbit(l)]=min(f[k][i][j^lowbit(l)],f[k][i][j]);
55     }
56     for(re int i=0;i<(1<<m);++i)
57         ans=min(ans,f[n+1][0][i]);
58     printf("%lld\n",ans);
59     return 0;
60 }
View Code

T2:

想着打区间的平衡树,还没打出来,90分咕咕

T3:

随机化真没有啥好说的,好在我没有去想记录路径,那样是错的

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 #include<algorithm>
 5 #include<queue>
 6 #define int long long
 7 #define re register
 8 using namespace std;
 9 const int MAXN=1005,MAXM=2005;
10 int n,m,dis[2][MAXN],maxx=0,tot;
11 struct node{
12     int u,v,w;
13 }e[MAXM];
14 int to[MAXM<<1],nxt[MAXM<<1],pre[MAXN],val[MAXM<<1],cnt=0;
15 inline void add(re int u,re int v,re int w){
16     ++cnt,to[cnt]=v,nxt[cnt]=pre[u],pre[u]=cnt,val[cnt]=w;
17 }
18 priority_queue< pair<int,int> >q;
19 bool vis[MAXN],in[MAXN];
20 inline void dijkstra(re int s){
21     memset(vis,0,sizeof(vis));
22     re int t=s;
23     if(s==1) s=0;
24     else s=1;
25     dis[s][t]=0;
26     q.push(make_pair(0,t));
27     while(!q.empty()){
28         re int x=q.top().second;
29         q.pop();
30         if(vis[x]) continue;
31         vis[x]=1;
32         for(re int i=pre[x];i;i=nxt[i]){
33             re int y=to[i];
34             if(dis[s][y]>dis[s][x]+val[i]){
35                 dis[s][y]=dis[s][x]+val[i];
36                 q.push(make_pair(-dis[s][y],y));
37             }
38         }
39     }
40 }
41 signed main(){
42     scanf("%lld%lld",&n,&m);
43     for(re int i=1,u,v,w;i<=m;++i){
44         scanf("%lld%lld%lld",&u,&v,&w);
45         e[i]=(node){u,v,w};
46         if(w==-1) w=0;
47         add(u,v,w),add(v,u,w);
48         maxx=max(maxx,w);
49     }
50     memset(dis,0x3f,sizeof(dis));
51     dijkstra(1),dijkstra(n);
52     for(re int i=1;i<=n;++i){
53         if(dis[0][n]>=dis[0][i]+dis[1][i]){
54             tot+=(in[i]==0);
55             in[i]=1;
56         }
57     }
58     memset(pre,0,sizeof(pre));
59     cnt=0;
60     for(re int i=1;i<=m;++i){
61         re int u=e[i].u,v=e[i].v,w=e[i].w;
62         if(w==-1) w=0x3f3f3f3f3f3f3f3f;
63         add(u,v,w),add(v,u,w);
64     }
65     memset(dis,0x3f,sizeof(dis));
66     dijkstra(1),dijkstra(n);
67     for(re int i=1;i<=n;++i){
68         if(dis[0][n]>=dis[0][i]+dis[1][i]){
69             tot+=(in[i]==0);
70             in[i]=1;
71         }
72     }
73     srand(time(0));
74     for(re int k=1;k*(n+m)*10<=4e7;++k){
75         if(tot==n) break;
76         re int ww=rand()%(maxx*2)+1;
77         memset(pre,0,sizeof(pre));
78         cnt=0;
79         for(re int i=1;i<=m;++i){
80             re int u=e[i].u,v=e[i].v,w=e[i].w;
81             if(w==-1) w=ww;
82             add(u,v,w),add(v,u,w);
83         }
84         memset(dis,0x3f,sizeof(dis));
85         dijkstra(1),dijkstra(n);
86         for(re int i=1;i<=n;++i){
87             if(dis[0][n]>=dis[0][i]+dis[1][i]){
88                 tot+=(in[i]==0);
89                 in[i]=1;
90             }
91         }
92         //cout<<res<<endl;
93     }
94     for(int i=1,res;i<=n;++i){
95         printf("%lld",res=in[i]);
96     }
97     puts("");
98     return 0;
99 }
View Code

T1:

就是那个式子,不会证

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 #include<algorithm>
 5 #define int long long
 6 using namespace std;
 7 const int mod=998244353;
 8 int t,n;
 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     scanf("%lld",&t);
20     while(t--){
21         scanf("%lld",&n);
22         printf("%lld\n",(n%mod*(n%mod)%mod-1+mod)%mod*q_pow(9,mod-2,mod)%mod);
23     }
24     return 0;
25 }
View Code

T2:

设f[i]为以i结尾的后缀个数,g[i]为以i为起点的前缀个数,hash优化统计

这样有90分

然后trie树上dfs优化统计,加上unordered_map就不会被卡了

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 #include<unordered_map>
 5 #define int long long
 6 #define ull unsigned long long
 7 using namespace std;
 8 const int MAXN=1e5+5,k=13331;
 9 char s[MAXN],a[MAXN];
10 int n,len,la,ans=0;
11 ull hs1[MAXN],hs2[MAXN],pre[MAXN];
12 int tr1[MAXN<<1][27],tr2[MAXN<<1][27],cnt1=1,cnt2=1;
13 unordered_map<ull,int>mp1,mp2;
14 void insert(int la){
15     ull ha=0;
16     int root=1;
17     for(int i=1;i<=la;++i){
18         ha=ha*k+a[i];
19         if(!tr1[root][a[i]-'a']) tr1[root][a[i]-'a']=++cnt1;
20         if(mp1.find(ha)==mp1.end()) mp1[ha]=1;
21         else ++mp1[ha];
22         root=tr1[root][a[i]-'a'];
23     }
24     ha=0,root=1;
25     for(int i=la;i>=1;--i){
26         ha=ha*k+a[i];
27         if(!tr2[root][a[i]-'a']) tr2[root][a[i]-'a']=++cnt2;
28         if(mp2.find(ha)==mp2.end()) mp2[ha]=1;
29         else ++mp2[ha];
30         root=tr2[root][a[i]-'a'];
31     }
32 }
33 void dfs1(int now,ull ha){
34     for(int i=0;i<26;++i){
35         if(tr1[now][i]){
36             int t=ha*k+i+'a',p=mp1[ha];
37             if(mp1.find(t)==mp1.end()) mp1[t]=p;
38             else mp1[t]+=p;
39             dfs1(tr1[now][i],t);
40         }
41     }
42 }
43 void dfs2(int now,ull ha){
44     for(int i=0;i<26;++i){
45         if(tr2[now][i]){
46             int t=ha*k+i+'a',p=mp2[ha];
47             if(mp2.find(t)==mp2.end()) mp2[t]=p;
48             else mp2[t]+=p;
49             dfs2(tr2[now][i],t);
50         }
51     }
52 }
53 int f(int x){//houzhui
54     int l=1,r=x,res=0;
55     while(l<=r){
56         int mid=(l+r)>>1;
57         if(mp2.find(hs2[mid]-hs2[x+1]*pre[x-mid+1])==mp2.end()) l=mid+1;
58         else res=mp2[hs2[mid]-hs2[x+1]*pre[x-mid+1]],r=mid-1;
59     }
60     return res;
61 }
62 int g(int x){//qianzhui
63     int l=x+1,r=len,res=0;
64     while(l<=r){
65         int mid=(l+r)>>1;
66         if(mp1.find(hs1[mid]-hs1[x]*pre[mid-x])==mp1.end()) r=mid-1;
67         else res=mp1[hs1[mid]-hs1[x]*pre[mid-x]],l=mid+1;
68     }
69     return res;
70 }
71 signed main(){
72     scanf("%s",s+1);
73     len=strlen(s+1);
74     pre[0]=1;
75     for(int i=1;i<=len;++i){
76         pre[i]=pre[i-1]*k;
77         hs1[i]=hs1[i-1]*k+s[i];
78     }
79     for(int i=len;i>=1;--i){
80         hs2[i]=hs2[i+1]*k+s[i];
81     }
82     scanf("%lld",&n);
83     for(int i=1;i<=n;++i){
84         scanf("%s",a+1);
85         la=strlen(a+1);
86         insert(la);
87     }
88     dfs1(1,0);dfs2(1,0);
89     for(int i=1;i<len;++i){
90         ans+=f(i)*g(i);
91     }
92     printf("%lld\n",ans);
93     return 0;
94 }
View Code

T3:

前80分大力分类讨论

后面要推式子,还没推出来,先咕在这里了

01-03 02:42