11.2 模拟赛小记

标签：map 10 int ll long 11.2 ans 模拟小记

赛时记录：

5min：瞄了一眼题，感觉今天的部分分还是很多。写了一点目标分数和做题计划，就开始看 T1。很明显的 dij，但想怎么转点权。

15min：点权转边权多源最短路，考虑建反边 + 超级源点就能完美解决。开写。

代码实现用了 5min 但答案不对。

哦，输出魅力值最高的城市。写成魅力值最高了。

嗯。map 了一下，过样例了。写对拍测大样例。

35 min：对拍能力较弱。刚拍完。以后多练练。也检查出了错：数组开小 + 没开 long long（主要是，题面说 a<= 1e9 但是大样例有 6e9 好像。不管了，总之更保险。拍都过了，开 B。

50min：写完了暴力。大概是 60pts 的？测一下大样例。

然后过了前 60% 的大样例。休息一下开 C。

额。感觉 C 有些复杂。开一下 D 。感觉 D 的暴力很好写的说。

蚌，还挺，不好写的。

80 min：我已经有 160pts 了。所以我需要写个 D 的哈希。嗯。

95 min：喜报，写不动。

110 min：测大样例为什么 n^2 跑不过。有些 b 溃。写假了？

120 min：妈的才发现 B 是 30 pts 啊。

130 min：妈的，谁告诉你是 n^2。map 是 log(n) 啊。

135 min：wflbb。。。想正难则反，n * m 减去出现的。结果发现 ans2 就是 n * m。。要你这 b 大样例有何用。

这个煞笔愿意花 2h 磕 D。感觉能写个性质。。。

200min：额。写了个性质。其他大的直接输出 n * m。b 溃地看看 B。

205min：看 B，感觉类似的正难则反：找拼出的 k 的倍数。

可以找两个对 k 取模相加为 k 的数。好像用 map 就行。

然后这个煞笔发现还有 50min。写个什么好呢。写个 C 吧。

240 min：啊哈！发现读不懂 C。然后再看 B 以及等吃饭。

没想到 TruE 是唯一一个开始播放不卡的。爱门。

最后反正没调出来。感觉很，失败。

以上是赛时记录。下面部分是赛后。

刚开始看题，一个计划得分是 100+60+10+40。

最后的得分是 100+30+0+80。

今天的题确实简单嗯。另一方面 t4 数据也太水了吧。

A.travel

有向图中求对于每个点能到达的点权最大的点的编号。每个点的点权唯一。

想了想，之前好像见过类似的套路，不难想到建反图 + 一个超级源点。因为点权唯一所以用 map 存。

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N=1e6+10;
int n,m;
int a[N];
int vis[N];
int idx,e[N],nxt[N],head[N];
ll w[N],ans[N];
priority_queue<pair<ll,int> > q;
map<ll,int> vn;
void add(int x,int y,ll z){
	e[++idx]=y;
	w[idx]=z;
	nxt[idx]=head[x];
	head[x]=idx;
}
void dij(){
	q.push(make_pair(0,n+1));
	while(q.size()){
		int x=q.top().second;
		q.pop();
		if(vis[x]) continue;
		vis[x]=1;
		for(int i=head[x];i;i=nxt[i]){
			if(ans[e[i]]<max(ans[x],w[i])){
				ans[e[i]]=max(ans[x],w[i]);
				q.push(make_pair(ans[e[i]],e[i]));
			}
		}
	}
}
int main(){
//	freopen("travel.in","r",stdin);
//	freopen("travel.out","w",stdout);
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++){
		scanf("%lld",&a[i]);
		vn[a[i]]=i;
	}
	while(m--){
		int x,y;
		scanf("%d%d",&x,&y);
		add(y,x,a[y]);
	}
	for(int i=1;i<=n;i++) add(n+1,i,a[i]);
	dij();
	for(int i=1;i<=n;i++){
		if(a[i]>ans[i]) printf("%d ",i);
		else printf("%d ",vn[ans[i]]);
	}
	return 0;
}

B.piece

给一个数字序列 \(a_i\)。将两个数拼起来，如 123 和 456 拼起来就是 123456（哪个串在前也会有不同的影响）。求得到新数非 k 的倍数的个数。

机子太慢卡掉了很多人的正解。可惜我一直看 D 没调完 B。这又是一个考场策略问题。

赛时写的 \(n * 2\) 的暴力。

赛后老师开讲，才发现第二部分数据，\(n <=1e5，a <=1e3\) 时可以直接桶排。啊好聪明。希望记住这种方法。这 30pts 可以说非常不该失掉。

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N=1e5+10;
ll ans;
int n,m;
int a[N];
int ten[N];
int t[N],tot;
map<int,int> cnt;
bool pd(int x,int y){
	ll t=y;
	int len=0;
	while(t){
		t/=10;
		len++; 
	}
	return ((ll)x*ten[len]+y)%m;
}
int main(){
	ten[0]=1;
	for(int i=1;i<=12;i++) ten[i]=ten[i-1]*10;
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++){
		scanf("%d",&a[i]);
		if(!cnt[a[i]]) t[++tot]=a[i];
		cnt[a[i]]++;
	}
	sort(t+1,t+tot+1);
	for(int i=1;i<=tot;i++){
		for(int j=1;j<=tot;j++){
			if(pd(t[i],t[j])){
				if(i==j) ans+=(ll)cnt[t[i]]*(cnt[t[j]]-1);
				else ans+=(ll)cnt[t[i]]*cnt[t[j]];
			}
		}
	}
	printf("%lld",ans);
}

后来进一步想了想，加了些细节，就过了。赛时思路已经很接近正解了。

首先一个最近见了好几次的、挺常见的套路：k 的倍数即 \(mod \text{ k=0}\)。

有时候发现 k 巨大，没关系，当 n 并没有那么大的时候你会发现其实其实 map 一下能存下了。

然后两个数接起来，就是 \(x * 10^{len_y}+y\)，其中 \(len_y\) 就是这个数字的位数。

因为 \(a_i<=1e9\) 每个数字位数不超过 9 位，所以可以把每个数字对于每个 \(10^i\) 乘起来预处理一下。这里注意一求 \(10^i\) 定要即使取模！！！

对于所以出现的余数 \(t_i\)，遍历以这个为余数的数 \(j\)。要求余数为 0，即处理后的这两个数对于 \(k\) 的余数相加为 \(k\) 或 \(0+0\)。但是自己和自己是拼不起来的，需要特判减掉。

然后本题时间卡的非常严格，跑的飞慢。long long 不能少开，开多了又容易炸，比较难调。

比较套路，我觉得不是很难。

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N=1e5+10;
ll ans,k;
int tot,n;
ll ten[12];
ll a[N],t[N];
int len[N];
map<ll,vector<int> > cnt;
map<ll,int> mod[12];
void get(int i){
	ll x=a[i];
	while(x){
		x/=10;
		len[i]++;
	}
}
int main(){
	scanf("%d%lld",&n,&k);
	ten[0]=1;
	for(int i=1;i<=10;i++) ten[i]=(ten[i-1]*10)%k;//一定记得取模
	for(int i=1;i<=n;i++){
		scanf("%lld",&a[i]);
		if(!cnt[a[i]%k].size()){
			t[++tot]=a[i]%k;//统计余数
		}
		cnt[a[i]%k].push_back(i);
		for(int j=1;j<=10;j++){
			mod[j][(a[i]*ten[j])%k]++;//预处理
		}
		get(i);//求位数
	}
	sort(t+1,t+tot+1);
	for(int i=1;i<=tot;i++){
		int q;
		if(t[i]==0) q=0;
		else q=k-t[i];
		for(auto j:cnt[t[i]]){
			ans+=mod[len[j]][q];
			if(((a[j]%k)*ten[len[j]])%k==q) ans--;//别忘了
		}
	}
	printf("%lld",((ll)n*(ll)(n-1))-ans);
}

C.flow

虽然和网络流有关系但不多，但感觉很不好写，因此并没有写。一方面是时间不够，另一方面是没读懂题。

比较复杂。听完讲解并没有懂多少。不可做，也不打算补题了。

D.cut

给定两个串，问用这两个串的非空前缀能拼出的不同字符串有多少个。

没猜错的话分数那么高是，若随机字符串的话很难出现答案，此时结果就是 n * m。大概这个骗到分了。

赛时写的小范围 o(n^2 * log(n))，特判了当第二个串都为 a 时的答案，其他输出 n * m。

这是我赛时丑陋的码：

#include<bits/stdc++.h>
#define ull unsigned long long
#define ll long long
using namespace std;
const int N=2e5+19;
int n,m;
int flag=1;
string a,b,s;
ll ans;
ull f1[N],f2[N],p[N];
map<ull,int> cnt;
void sub3(){
	int tot=0;
	for(int i=1;i<n;i++) if(a[i]=='a') tot++;
	printf("%lld",(ll)n*m-(ll)tot*(m-1));
}
void Hash(){
	p[0]=1;
	for(int i=1;i<=n;i++){
		f1[i]=f1[i-1]*131+(a[i-1]-'a'+1);
		p[i]=p[i-1]*131;
	}
	for(int i=1;i<=m;i++){
		f2[i]=f2[i-1]*131+(b[i-1]-'a'+1);
	}
}
int main(){
	//freopen("cut.in","r",stdin);
	//freopen("cut.out","w",stdout);
	cin>>a>>b;
	n=a.length(),m=b.length();
	for(int i=0;i<m;i++) if(b[i]!='a') {flag=0;break;}
	if(flag){sub3();return 0;}
	if(n>500){
		printf("%lld",(ll)n*m);
		return 0;
	}
	Hash();
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			ull t=f1[i]*p[j]+f2[j];
			if(!cnt[t]){
				ans++;
				cnt[t]=1;
			}
		}
	}
	printf("%lld",ans);
}

其实写完那个性质之后，思路就挺靠近正解了吧。大概是找第一个串的子串中和第二个串的一些前缀串的相同的，统计答案。

然后然后，我草，发现，很像，KMP。

妈的，这下小丑是我了。n * m 70pts 有笑的我。一看就没好好造数据。能想到 n * m 还是得益于第二个大样例就是 n * m。

下面的是标程。我 kmp 学的很差，正在恶补中，再次咕咕。搞懂后再回来写思路 qwq。

#include<bits/stdc++.h>
#define ll long long 
using namespace std;
const int N=1e5+10;
int n,m;
ll ans;
int nxt[N],cnt[N];
char s[N],t[N];
int main(){
	scanf("%s%s",s+1,t+1);
	n=strlen(s+1),m=strlen(t+1);
	for(int i=2,j=0;i<=m;i++){
		while(j&&t[j+1]!=t[i]) j=nxt[j];
		if(t[j+1]==t[i]) j++;
		nxt[i]=j;
	}
	for(int i=1,j=0;i<=n;i++){
		while(j&&t[j+1]!=s[i]) j=nxt[j];
		if(t[j+1]==s[i]) j++;
		if(j<i) cnt[j]++;
		else cnt[nxt[j]]++;
	}
	for(int i=m;i;i--) cnt[nxt[i]]+=cnt[i];
	ans=(ll)n*m;
	for(int i=1;i<=m;i++){
		if(nxt[i]&&i>nxt[i]) ans-=cnt[i-nxt[i]];
	}
	printf("%lld",ans);
}

总之，本题学到的是，有时候赌一把猜猜答案还挺重要的，尤其是出题人懒惰的随数据的时候。

写在最后的最后。听模拟赛讲解听到一半因为有别的老师讲课于是就让讲解老师自己一个人讲下去，甚至没有给他说一声。讲解老师强强的，可可爱爱的，但我们只能看他嘴一张一合但听不见声音了。我不好评价。我觉得很没有礼貌而且这是很不好的。

最后把极域关了，我也就不难受了。

今日小结：

1.发现模拟赛前半部分效率高，后半部分效率低；上半天效率高，下半天效率低。这是不好的。

2.测数据的时候看看有没有和代码放到同一个文件夹下。

3.多练练对拍。

4.合理分配时间。一定估计好时间。

5.从部分分中思考性质，深挖正解。

6.暴力打满好吧。

标签：map,10,int,ll,long,11.2,ans,模拟,小记
From： https://www.cnblogs.com/Moyyer-suiy/p/17806363.html

相关文章

赞助商

阅读排行