C/C++教程

20210819 Emotional Flutter,Medium Counting,Huge Counting,字符消除2

本文主要是介绍20210819 Emotional Flutter,Medium Counting,Huge Counting,字符消除2，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

考场

T1 一下想到了这题，将白块缩短 \(s\) 后维护类似的区间即可。
T2 T3 俩计数，直接跳了。
T4 的可行 \(t\) 集合相同相当与从 \(n\) 往前跳 kmp 数组，途径点相同，从前往后构造即可。

问题是可能会出现一个区间分裂成好几个（开个队列），\(k\) 很小而 \(a_i\) 很大（每次跳到块尾），然后一直调到 10.20 还过不了拍，先丢了。
写完 T2 T3 俩暴力，发现 T4 \(2\times kmp[i]<i\) 的时候中间不知道填啥，不能全填 \(0/1\)，然后一直手玩样例，三个样例总有一个过不去。。。
快结束的时候看了眼 T1，把每次跳到块尾的操作删了就过拍了，想着题面说数据有梯度，就交了个宁愿 T 的

res

rk19 0+0+15+0
T1 T2 全 T 了
T4 就是中间部分错了

rk1 yzf 100+100+40+20
rk2 szs 100+0+100+0
rk5 zjj 90+0+10+0
rk5 mtr 100+0+0+0
rk10 ycx 10+0+10+30
rk18 zkx 0+0+25+0

总结

其实没啥说的，就是菜

这场前面的人基本都 A 了 T1，但我考场上完全没往同余上想，有一个思路就面向数据编程，一直调，这样极容易暴毙，以后只有在确定算法正确性、复杂度的情况且其他题打满暴力的情况下再肝题。

这次虽然打了暴力但 T2 全 T 了，打暴力也算下复杂度，如果卡的紧就尽量剪剪枝。

sol

T1

每次跳到的位置模 \(k\) 同余，将黑块延长 \(s\) 后模 \(k\)，如果 \([0,k)\) 中出现了一个点没被黑块覆盖说明有解。细节比较多。






T4

const int N = 2e5+1;
int T;
char s[N];

int n,n1,f[N],g[N],pos[N];

void kmp(int *nxt,int l,int r) {
	for(int i = l+1, j = nxt[l]; i <= r; ++i) {
		while( j && s[j+1] != s[i] ) j = nxt[j];
		if( s[j+1] == s[i] ) ++j;
		nxt[i] = j;
	}
}
bool check(int u) {
	for(; u; u = f[u]) if( f[u] != g[u] ) return 0;
	return 1;
}
void solve() {
	scanf("%s",s+1); n = strlen(s+1);
	kmp(f,1,n);
	For(i,1,n) s[i] = '0'; s[n+1] = 0;
	for(int i = n; i; i = f[i]) pos[++n1] = i; reverse(pos+1,pos+n1+1);
	s[pos[1]] = '0'+(pos[1]!=1), kmp(g,1,pos[1]);
	For(i,2,n1) {
		if( pos[i-1]*2 >= pos[i] )
			For(j,pos[i-1]+1,pos[i]) s[j] = s[pos[i-1]-(pos[i]-j)];
		else {
			For(j,pos[i]-pos[i-1]+1,pos[i]) s[j] = s[pos[i-1]-(pos[i]-j)];
			kmp(g,pos[i-1],pos[i]);
			if( !check(pos[i]) ) s[pos[i]-pos[i-1]] = '1';
		}
		kmp(g,pos[i-1],pos[i]);
	}
	printf("%s\n",s+1);
}

signed main() {
	scanf("%d",&T);
	while( T-- ) {
		n1 = 0;
		solve();
	}
	return iocl();
}






吐嘈


T1 题面说的“数据有梯度”恐怕指的是一个测试点内每组数据有梯度，不会正解的人只能拿到 0/10pts，导致今天爆 \(0\) 的人格外多。


虽然这次的题是拼的，但看 T2 T3 的原比赛出了 \(3\) 道计数，让我这种计数很弱的人体验极差。


T4 貌似是模拟赛中第一次出构造

                    

                        这篇关于20210819 Emotional Flutter,Medium Counting,Huge Counting,字符消除2的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！
                    


                


                
                
 

                
                

                    

                        
您可能喜欢

                        
                    

                

                

            

             
            
            
            
        

        
        

        

            

                
栏目导航