专栏文章

题解：CF1142D Foreigner

DDovish
CF1142D题解参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@min3z2wi
此快照首次捕获于
2025/12/01 20:11
3 个月前
此快照最后确认于
2025/12/01 20:11
3 个月前
查看原文
其实是找规律题的。

题解

判定一个数 xx 是否合法需要知道 ⌊x10⌋\lfloor\dfrac{x}{10}\rfloor 是否合法以及其排名。
那么一个朴素暴力的想法就是：枚举左端点，不断向右拓展合法的状态。
不过我们这个过程中需要在一个数末尾追加上一个数位，如何计算排名的变化呢？
发现我们本质上只需要计算排名在  mod 11\bmod 11 下的值即可。
然后打表找一下规律，发现：如果我们知道 xx 的排名，则 10x10x 的排名总是一定的（在  mod 11\bmod {11} 意义下）。
具体而言，对应关系如下：
rank(x)rank(10x)
0不存在
110
20
32
45
59
63
79
85
92
100
所以我们可以写出以下暴力：
CPP
int tr[11]={-1,10,0,2,5,9,3,9,5,2,0};
void solve()
{
	rep(i,1,n)
	{
		if(!a[i])continue;
		int rk=10; 
		rep(j,i,n)
		{
			if(a[j]>=rk)break;
			ans++;
			rk=(tr[rk]+a[j])%11;
		}
	}
}
优化这个是容易做的，我们设 fi,cf_{i,c} 表示在 ii 的位置传入 cc 的 rk，最早会在什么时刻使得 aj≥rka_j\ge rk。
转移计算一下传入下一个位置的排名即可。
复杂度 O(np)O(np)，其中 pp 是模数，本题中 p=11p=11。

code

CPP
#include<bits/stdc++.h>
#define int long long
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
#define per(i,a,b) for(int i=(a);i>=(b);--i)
#define edge(i,u) for(int i=head[u];i;i=e[i].next)
#define lc(u) (u<<1)
#define rc(u) (u<<1|1)
#define pii pair<int,int>
#define mp make_pair
#define pb push_back
#define fst first
#define sed second
using namespace std;
const int N=1e5+10;
bool MS;int used;
int a[N];
string s;
int n,ans;
int tr[11]={-1,10,0,2,5,9,3,9,5,2,0};
int f[N][11];
bool MT;
signed main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin>>s;
	n=s.size();
	s=" "+s;
	rep(i,1,n)
	a[i]=s[i]-'0';
	ans=0;
	rep(c,0,10)f[n+1][c]=n+1;
	per(i,n,1)
	{
		rep(c,0,10)
		{
			if(a[i]>=c)f[i][c]=i;
			else f[i][c]=f[i+1][(tr[c]+a[i])%11];
		}
		if(!a[i])continue;
		ans+=f[i][10]-i;
	}
	cout<<ans<<'\n';
	cerr<<"Memory:"<<(&MS-&MT)/1048576.0<<"MB Time:"<<clock()/1000.0<<"s\n";
}

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...