智算之道初赛第一场三道题题解

eg：好奇怪的比赛，ioi赛制，排名竟然是按照最后一个点的时间和算的，当即变成优化常数大赛，实在是不知道第一聚聚怎么做到三道题0ms的，感觉我已经用尽毕生的优化常数黑科技了。

排队

题意：有n个人从1到n标号，m次操作，每次操作将n个人里标号为x的整数倍的人删除，问还剩多少人。
题解：筛法，加上快读并且把int数组改成bool数组之后就0ms了。

#include<stdio.h>
using namespace std;
int read(){
    int f=1,x=0;char ch;
    do{ch=getchar();if(ch=='-')f=-1;}while(ch<'0'||ch>'9');
    do{x=x*10+ch-'0';ch=getchar();}while(ch>='0'&&ch<='9');
    return f*x;
}
bool f[100000+10]; 
int n,m; 
int main(){
	n=read();m=read(); 
	for(int i=1;i<=m;i++){
		int x;
		x=read();
		if(f[x]==false){
			for(int j=x;j<=n;j+=x)
				f[j]=true;
		}
	}
	int ans=0;
	for(int i=1;i<=n;i++)
		if(f[i]==false)ans++;
	printf("%d\n",ans);
	return 0;
}

开关

题意：长度n的01串，每次可以选择一个位置x，该位置及该位置前的所有0和1取反，问变成全0串的最少次数。
题解：最高位向最低位枚举即可，第一发3ms，然后加上快读getchar和register等操作之后是2ms，不记得本地存的是几ms的代码了。

#include<stdio.h>
#pragma GCC optimize(2)
using namespace std;
inline int read(){
    int f=1,x=0;char ch;
    do{ch=getchar();if(ch=='-')f=-1;}while(ch<'0'||ch>'9');
    do{x=x*10+ch-'0';ch=getchar();}while(ch>='0'&&ch<='9');
    return f*x;
}
int n,num=0;
char s[200000+10],ch;
int main(){
	n=read();
    while(true){
    	ch=getchar();
    	if(ch=='\n')break;
    	s[num++]=ch;
    }
	int ans=0;
	bool cnt=false;
	for(register int i=n-1;i>=0;i--){
		if(cnt==false){
			if(s[i]=='1')ans++,cnt=true;
		}else{
			if(s[i]=='0')ans++,cnt=false;
		}
	}
	printf("%d\n",ans);
	return 0;
}

字符串

题意：给两个串S和T，问T中有多少子串经过重排之后可以成为S串。
题解：还以为是什么后缀自动机之类的狠题，注意到重排之后可以成为S串，实际上只要字母和S串对应相等即可。之后使用类似滑窗手法确定区间，如果字母对应相等，则存在区间哈希值，之后去重即可。一开始写的map存的600+ms，改成数组，同时inline什么的也造上，依旧不低。最后用vector+sort去重，删掉了set优化到了18ms，队友优化到12ms我是没想到的。。

#include<stdio.h> 
#include<vector>
#include<map>
#include<string.h>
#include<algorithm>
#include<iostream>
#pragma GCC optimize(2)
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const int N=2e5+10;
const ull p=131;
ull Hash[N];
ull po[N];
vector<ull>ss; 
char s[N],t[N];
int n,m;
int mp[200],mp2[200];
inline ull getHash(int l,int r){
	if(l==0)return Hash[r];
	return Hash[r]-Hash[l-1]*po[r-l+1];
}
int main(){
	scanf("%s",&s);
	scanf("%s",&t);
	n=strlen(s),m=strlen(t);
	for(register int i=0;i<n;i++)mp[s[i]-'a']++;
	po[0]=1;
	Hash[0]=t[0]-'a';
	for(register int i=1;i<m;i++){
		Hash[i]=Hash[i-1]*p+t[i]-'a';
		po[i]=po[i-1]*p;
	}
	for(register int i=0;i<n;i++)mp2[t[i]-'a']++;
	for(register int i=n;i<=m;i++){
		bool flag=false;
		for(int j=0;j<26;j++)
			if(mp[j]!=mp2[j]){
				flag=true;
				break;
			}
		if(flag==false)ss.push_back(getHash(i-n,i-1));
		if(i==m)break;
		mp2[t[i-n]-'a']--,mp2[t[i]-'a']++;
	}
	sort(ss.begin(),ss.end());
	int k=ss.size(),ans=ss.size();
	for(register int i=1;i<k;i++)
		if(ss[i-1]==ss[i])ans--;
	printf("%d\n",ans);
	return 0;
}

最后

优化大赛挺好玩的，但还有个队友竟然没有ak真是太水了点= =！我在群里说xjb优化，竟然有人这么回复，一时间竟不知道是节目效果还是故意的。。