20230914 比赛总结

反思

A

一想到思路就立马开始写，考完才知道自己写烦了很多

B

数组开小！数组开小！
随机大法好！随机大法好！

C

没有想到用图像来直观显示每个 $1$ 的变化曲线，感觉套路看得太少了

题解

比赛链接

A

我是sb，写 $ntt$

B

看到这种极度不可做的题，一定要想到随机化与哈希！！！
可以想到给每个点随机分一个较小的权值，然后跑状压 $dp$，我分的权值范围是 $[0,k+2)$，那么每次的正确率就是 $\frac{k!}{(k+2{)}^k}$
多跑几次既可，可以掐一下时间
但我是sb，数组开小了10倍

#include 
using namespace std;
const int N=30100,M=200100,MAXS=1100;
int n,m,k,dp[N][MAXS],val[N];
int e[M],ne[M],w[M],h[N],idx;
inline int read(){
	int FF=0,RR=1;
	char ch=getchar();
	for(;!isdigit(ch);ch=getchar()) if(ch=='-') RR=-1;
	for(;isdigit(ch);ch=getchar()) FF=(FF<<1)+(FF<<3)+ch-48;
	return FF*RR;
}
void add(int x,int y,int z){ e[idx]=y,w[idx]=z,ne[idx]=h[x],h[x]=idx++;}
inline void chkmax(int &x,int y){ x=max(x,y);}
int work(){
	for(int i=1;i<=n;i++) val[i]=rand()%(k+2);
    // for(int i=1;i<=n;i++) cout<
    for(int i=1;i<=n;i++) for(int j=0;j<1<<(k+2);j++) dp[i][j]=-1;
	for(int i=1;i<=n;i++) dp[i][1<<val[i]]=0;
    for(int S=0;S<1<<(k+2);S++){
        if(__builtin_popcount(S)>=k) continue;
        for(int i=1;i<=n;i++){
            if(dp[i][S]<0) continue;
            for(int j=h[i];~j;j=ne[j]){
                int v=e[j];
                if(!(S>>val[v]&1)) chkmax(dp[v][S^1<<val[v]],dp[i][S]+w[j]);
            }
        //    cout<
        }
    }
	int ans=0;
	for(int i=1;i<=n;i++) for(int S=0;S<1<<(k+2);S++) if(__builtin_popcount(S)==k) ans=max(ans,dp[i][S]);
	return ans;
}
int main(){
    freopen("graph.in","r",stdin);
    freopen("graph.out","w",stdout);
	srand(time(NULL));
	n=read(),m=read(),k=read();
    memset(h,-1,sizeof(h));
    for(int i=1;i<=m;i++){
        int x=read(),y=read(),z=read();
        add(x,y,z),add(y,x,z);
    }
	int ans=0;
	while(1.0*clock()/CLOCKS_PER_SEC<3.7) ans=max(ans,work());
	printf("%d\n",ans);
	fprintf(stderr,"%d ms\n",int(1e3*clock()/CLOCKS_PER_SEC));
	return 0;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51

C

妙妙题！
考虑每个 $1$ 的路径一定是一个 $t-s$ 的分段函数，考虑维护这个分段函数
注意到每个 $1$ 的分段函数一定只和上一个 $1$ 的分段函数有关
所以考虑修改上一个分段函数
考虑到最小的一个不可以往前移的时间，这个时间前面一定是一段递减区间，后面一定是上一个分段函数往右上平移得来的
所以考虑整体打 $tag$，然后让新加的区间适应这个 $tag$ 既可
用 $deque$ 维护，时间复杂度 $O(n)$

#include 
using namespace std;
typedef pair<int,int> pii;
const int N=3000100;
int n,T,a[N],ans[N];
deque<pii> deq;
inline int read(){
	int FF=0,RR=1;
	char ch=getchar();
	for(;!isdigit(ch);ch=getchar()) if(ch=='-') RR=-1;
	for(;isdigit(ch);ch=getchar()) FF=(FF<<1)+(FF<<3)+ch-48;
	return FF*RR;
}
int main(){
    freopen("seq.in","r",stdin);
    freopen("seq.out","w",stdout);
	n=read(),T=read();
	for(int i=1;i<=n;i++) a[i]=read();
	deq.push_back(make_pair(0,0)),deq.push_back(make_pair(T,0));
	int tag=0;
	for(int i=1;i<=n;i++){
		if(!a[i]) continue;
		while(!deq.empty()){
			int x=deq.front().first+tag;
            int y=deq.front().second+tag;
            // cout<
            if(i-x>y+1) deq.pop_front();
            else{
                int stop=i-(y+1);
                // cout<
                if(stop) deq.push_front(make_pair(stop-(tag+1),(y+1)-(tag+1)));
                deq.push_front(make_pair(-(tag+1),i-(tag+1)));
                break;
            }
		}
		tag++;
        if(deq.empty()) deq.push_back(make_pair(-tag,i-tag)),deq.push_back(make_pair(T-tag,i-T-tag));
        int tmp=-1;
        while(deq.back().first+tag>T){ tmp=deq.back().second;deq.pop_back();}
        if(tmp!=-1){
            int x=deq.back().first,y=deq.back().second;
            // cout<
            if(y==tmp) deq.push_back(make_pair(T-tag,tmp));
            else deq.push_back(make_pair(T-tag,y-(T-(x+tag))));
        }
		ans[deq.back().second+tag]=1;
	}
	for(int i=1;i<=n;i++) printf("%d ",ans[i]);puts("");
	fprintf(stderr,"%d ms\n",int(1e3*clock()/CLOCKS_PER_SEC));
	return 0;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52