链接
题目链接
题目
A. Accurate Movement
模拟即可。
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
| #include <bits/stdc++.h>
using namespace std;
#define FO(x) freopen(#x".in","r",stdin),freopen(#x".out","w",stdout)
#define fo(i,j,k) for(int i=(j),end_i=(k);i<=end_i;i++)
#define ff(i,j,k) for(int i=(j),end_i=(k);i< end_i;i++)
#define fd(i,j,k) for(int i=(j),end_i=(k);i>=end_i;i--)
#define DEBUG(x) cerr<<#x<<"="<<x<<endl
#define all(x) (x).begin(),(x).end()
#define cle(x) memset(x,0,sizeof(x))
#define lowbit(x) ((x)&-(x))
#define ll long long
#define ull unsigned ll
#define db double
#define lb long db
#define pb push_back
#define mp make_pair
#define fi first
#define se second
inline int read()
{
int x=0; char ch=getchar(); bool f=0;
for(;ch<'0'||ch>'9';ch=getchar()) if(ch=='-') f=1;
for(;ch>='0'&&ch<='9';ch=getchar()) x=(x<<3)+(x<<1)+(ch^48);
return f?-x:x;
}
#define CASET fo(___,1,read())
int a,b,n,ans;
int main()
{
a=read(); b=read(); n=read();
int d=b-a;
for(;b<n;)
{
if(a<n) a=b,ans++;
b+=d,ans++;
}
if(a<n) a=b,ans++;
printf("%d\n",ans);
return 0;
}
|
B. Bad Treap
题意
找出 $n$ 个在 int 范围内的整数，满足
$a_i<a_{i+1}$ 且 $\sin(a_i)<\sin(a_{i+1})$。
$n\le 50000$
题解
设 $a_i=k(i+b)$，那也就是要找一个整数 $k$，使得 $k>2\omega \pi$ 且 $k-2\omega \pi$ 的值尽量小。
打表发现，$k=710$ 效果很好。
C. Cross-Stitch
答案下界显然是 $4n-1$，其中 $n$ 为 X 的个数。
可以发现，每个 X 中距离为 $1$ 的情况只需要用到竖着的两条。因为只用竖着的两条，最终可以回到本身这个节点，也可以去到原节点同一列的节点上。
建出图后，跑个有限制的欧拉回路就可以了。
比赛的时候忘在dfs里加限制了。。。
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
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
| #include <bits/stdc++.h>
using namespace std;
#define FO(x) freopen(#x".in","r",stdin),freopen(#x".out","w",stdout)
#define fo(i,j,k) for(int i=(j),end_i=(k);i<=end_i;i++)
#define ff(i,j,k) for(int i=(j),end_i=(k);i< end_i;i++)
#define fd(i,j,k) for(int i=(j),end_i=(k);i>=end_i;i--)
#define DEBUG(x) cerr<<#x<<"="<<x<<endl
#define all(x) (x).begin(),(x).end()
#define cle(x) memset(x,0,sizeof(x))
#define lowbit(x) ((x)&-(x))
#define ll long long
#define ull unsigned ll
#define db double
#define lb long db
#define pb push_back
#define mp make_pair
#define fi first
#define se second
inline int read()
{
int x=0; char ch=getchar(); bool f=0;
for(;ch<'0'||ch>'9';ch=getchar()) if(ch=='-') f=1;
for(;ch>='0'&&ch<='9';ch=getchar()) x=(x<<3)+(x<<1)+(ch^48);
return f?-x:x;
}
#define CASET fo(___,1,read())
const int N=600000;
int n,m,st[N],top;
int ver[N],ne[N],head[N],tot=1,n1,n2;
bool vis[N];
inline void add(int x,int y)
{
ver[++tot]=y; ne[tot]=head[x]; head[x]=tot;
ver[++tot]=x; ne[tot]=head[y]; head[y]=tot;
}
inline int id(int x,int y,int z)
{
return x+y*n1+z*n2;
}
void dfs(int u,int las)
{
for(int &i=head[u];i;i=ne[i])
if(!vis[i]&&(las==-1||((u/n2)!=(ver[i]/n2)||(las!=ver[i]/n2))))
{
vis[i]=vis[i^1]=1;
dfs(ver[i],(u/n2)==(ver[i]/n2)?ver[i]/n2:-1);
}
st[++top]=u;
}
inline void pr(int x)
{
x%=n2;
printf("%d %d\n",x/n1,x%n1);
}
inline void print(int k)
{
if(k==1) return;
print(k-1);
if(abs(st[k]-st[k-1])!=n2)
pr(st[k]);
}
char s[105];
int sum;
int main()
{
n=read(); m=read();
swap(n,m);
n1=(max(n,m)+5); n2=(max(n,m)+5)*(max(n,m)+5);
int xx=-1,yy=-1;
fo(i,1,n)
{
scanf("%s",s+1);
fo(j,1,m)
if(s[j]=='X')
{
fo(a,0,1)
fo(b,0,1)
add(id(i-a,j-b,0),id(i-a,j-b,1));
add(id(i-1,j,1),id(i,j,1));
add(id(i-1,j-1,1),id(i,j-1,1));
add(id(i-1,j-1,0),id(i,j,0));
add(id(i-1,j,0),id(i,j-1,0));
xx=i; yy=j;
sum++;
}
}
if(xx==-1)
{
printf("-1\n");
return 0;
}
printf("%d\n",sum*4-1);
dfs(id(xx,yy,0),-1);
print(top);
return 0;
}
|
D. Double Palindrome
看来长时间没看，Border和回文理论有些忘了，在这写下证明吧QAQ。
一些证明
引理1(Weak Periodicity Lemma)：对一字符串 $s$，若 $p,q$ 为 $s$ 的周期，且 $p+q\le |s|$，则 $\gcd(p,q)$ 为 $s$ 的周期。
证明：
不妨设 $p\geq q$。设 $d=p-q$。
由 $p,q$ 为 $s$ 的周期，可知：$s_i=s_{i+p}(i\le |s|-p),s_i=s_{i+q}(i\le |s|-q)$。
当 $i> |q|$ 时，$s_i=s_{i-q}=s_{i-q+p}=s_{i+d}$。
当 $i\le |s|-p$ 时，$s_i=s_{i+p}=s_{i+p-q}=s_{i+d}$。
因此 $d=p-q$ 为 $s$ 的一个周期。
由辗转相除法，$\gcd(p,q)$ 为 $s$ 的周期。
证毕。
注意：真正的周期引理的限制条件可改为 $p+q-\gcd(p,q)\le |s|$。
引理2：若一字符串 $s$ 可以表示成至少两种不同的非空双回文划分，则字符串 $s$ 为整周期串。
证明：
记 $s[l,r]$ 表示字符串 $s$ 从第 $l$ 到第 $r$ 位形成的子串。
设 $s$ 的两种非空双回文划分为：$s[1,x]+s[x+1,|s|],s[1,y]+s[y+1,|s|]$，其中 $1\le x < y < |s|$，且 $s[1,x],s[x+1,s],s[1,y],s[y+1,|s|]$ 均为回文串。
可以发现，$y-x$ 和 $|s|-(y-x)$ 均为 $s$ 的周期，
由引理一，$\gcd(y-x,|s|-(y-x))=\gcd(y-x,|s|)$ 也为 $s$ 的周期。
而 $\gcd(y-x,|s|)|s$，证毕。
题意
用前 $k$ 个小写字符，组成长度至多为 $n$ 的字符串。
问有多少个串是弱双回文划分。
$n\le 10^5$，
题解
首先，设一个 $g(n)$ 表示暴力划分的双回文的种类数。
$g(n)=\sum_{i=1}^nk^{\lfloor \frac{i+1}{2}\rfloor}k^{\lfloor \frac{n-i+1}{2}\rfloor}$。
这样统计显然会算重，而多的自然是能被两种及以上划分的字符串。
由引理二，这样的字符串为整周期串。
于是，我们统计字符串的时候只统计只有一种划分的字符串，设长度为 $i$ 的合法字符串个数为 $f(i)$，那么答案就是 $\sum_{i=1}^nf(i)\lfloor \frac{n}{i} \rfloor$。
考虑求出 $f(n)$，用 $g(n)$ 减去不合法的方案，枚举整周期串的最小正周期 $i$，那么复制 $\frac{n}{i}$ 倍后形成的串就在 $g(n)$ 中算了 $\frac{n}{i}$ 次，减去即可。$f(n)=g(n)-\sum_{i\neq n,i|n} f(i)\frac{n}{i}$。
时间复杂度 $O(n\log n)$。
代码
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
| #include <bits/stdc++.h>
using namespace std;
#define FO(x) freopen(#x".in","r",stdin),freopen(#x".out","w",stdout)
#define fo(i,j,k) for(int i=(j),end_i=(k);i<=end_i;i++)
#define ff(i,j,k) for(int i=(j),end_i=(k);i< end_i;i++)
#define fd(i,j,k) for(int i=(j),end_i=(k);i>=end_i;i--)
#define DEBUG(x) cerr<<#x<<"="<<x<<endl
#define all(x) (x).begin(),(x).end()
#define cle(x) memset(x,0,sizeof(x))
#define lowbit(x) ((x)&-(x))
#define ll long long
#define ull unsigned ll
#define db double
#define lb long db
#define pb push_back
#define mp make_pair
#define fi first
#define se second
inline int read()
{
int x=0; char ch=getchar(); bool f=0;
for(;ch<'0'||ch>'9';ch=getchar()) if(ch=='-') f=1;
for(;ch>='0'&&ch<='9';ch=getchar()) x=(x<<3)+(x<<1)+(ch^48);
return f?-x:x;
}
#define CASET fo(___,1,read())
const ll mod=998244353;
inline ll Add(ll x,ll y){x+=y; return (x<mod)?x:x-mod;}
inline ll Dec(ll x,ll y){x-=y; return (x<0)?x+mod:x;}
inline ll Mul(ll x,ll y){return x*y%mod;}
inline ll Pow(ll x,ll y)
{
y%=(mod-1);ll ans=1;for(;y;y>>=1,x=x*x%mod)if(y&1) ans=ans*x%mod;
return ans;
}
int n,k;
ll f[100010],g[100010];
int main()
{
n=read(); k=read();
fo(i,1,n)
f[i]=g[i]=Add(Mul(i/2,Pow(k,(i+1)/2)),Mul((i+1)/2,Pow(k,(i+2)/2)));
fo(i,1,n)
fo(j,2,n/i)
f[i*j]=Dec(f[i*j],f[i]*j%mod);
ll ans=0;
fo(i,1,n)
ans=Add(ans,f[i]*(n/i)%mod);
printf("%lld\n",ans);
return 0;
}
|
E. Equidistant
题意
一棵树，给定 $m$ 个点，问是否存在一个点，使得该点到另外 $m$ 个点的距离相同。
$n,m\le 2\times 10^5$。
题解
$m$ 个点一起bfs即可。
代码
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
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
| #include <bits/stdc++.h>
using namespace std;
#define FO(x) freopen(#x".in","r",stdin),freopen(#x".out","w",stdout)
#define fo(i,j,k) for(int i=(j),end_i=(k);i<=end_i;i++)
#define ff(i,j,k) for(int i=(j),end_i=(k);i< end_i;i++)
#define fd(i,j,k) for(int i=(j),end_i=(k);i>=end_i;i--)
#define DEBUG(x) cerr<<#x<<"="<<x<<endl
#define all(x) (x).begin(),(x).end()
#define cle(x) memset(x,0,sizeof(x))
#define lowbit(x) ((x)&-(x))
#define ll long long
#define ull unsigned ll
#define db double
#define lb long db
#define pb push_back
#define mp make_pair
#define fi first
#define se second
inline int read()
{
int x=0; char ch=getchar(); bool f=0;
for(;ch<'0'||ch>'9';ch=getchar()) if(ch=='-') f=1;
for(;ch>='0'&&ch<='9';ch=getchar()) x=(x<<3)+(x<<1)+(ch^48);
return f?-x:x;
}
#define CASET fo(___,1,read())
const int N=200010;
vector<int> adj[N];
queue<int> q;
int n,m;
inline void add(int x,int y)
{
adj[x].pb(y); adj[y].pb(x);
}
int t[N],vis[N],d[N];
void bfs()
{
for(;!q.empty();)
{
int u=q.front(); q.pop();
if(t[u]==m)
{
printf("YES\n%d",u);
return;
}
for(auto v:adj[u])
{
if(!d[v]||d[v]==d[u]+1)
{
d[v]=d[u]+1;
t[v]+=t[u];
if(!vis[v])
{
vis[v]=1; q.push(v);
}
}
}
}
printf("NO");
}
int main()
{
n=read(); m=read();
fo(i,2,n) add(read(),read());
int x;
fo(i,1,m) x=read(),q.push(x),vis[x]=1,d[x]=1,t[x]=1;
bfs();
return 0;
}
|
H. High Load Database
题意
一个数组，将数组分为若干段连续的子段，使得每个子段之和不超过 $k$。
$m$ 次询问，每次询问给定 $k$，问最少的段数。
$n\le 2\times 10^5,q\le 10^5,\sum a_i\le 10^6,a_i\geq 1$。
题解
$\sum a_i\le 10^6$，可以发现对于每个 $k$，如果暴力用二分求出答案，时间复杂度大概是 $O(\frac{n}{k}\log n)$。
因此，通过记忆化的方法，$q$ 次询问总的最坏的复杂度就是 $O(n\log q\log n)$。
J. Just the Last Digit
从小到大枚举 $i$，枚举 $j$，然后判断 $i,j$ 是否有边相连。
判断的方法是算出除 $(i,j)$ 边外 $i$ 到 $j$ 路径条数模 $10$ 后的结果即可。
时间复杂度 $O(n^3)$。
L. Lengths and Periods
题意
对一字符串 $|s|$，设 $\alpha$ 为最大的 $\frac{|s|}{|t|}$，使得 $t$ 为 $s$ 的周期。
给定一字符串，问该字符串的子串最大的 $\alpha$ 是多少。
$|s|\le 2\times 10^5$。
题解
题目所求转换为：
选择任意两个后缀 $i,j(i<j)$，求出 $lcp(i,j)$，求 $\frac{lcp(i,j)+(j-i)}{j-i}$ 的最大值。
于是可以建出 SA，求出height数组，然后启发式合并即可。
时间复杂度 $O(n\log ^2n)$。