A.
题目描述：
数据范围：
题解：
代码：
B.
题目描述：
数据范围：
题解：
代码：
C.
题目描述：
数据范围：
题解：
代码：
题目描述：
$ [0,t] $ 区间，选择两个数 $ v_1, v_2 $ ，定义序列 $ X_0 = v_a + v_2 $ ， $ X_{n+1} = (aX_n + c) \mod m $ ，判断 $ X_{|v_1 - v_2|} $ 的奇偶
数据范围：
$ 1\le T \le 100 \\ 2\le m \le 10^6, 0 \le a, c \le m \\0 \le t \lt \frac{m}{2} $
题解：
看了下题解发现需要使用环套树森林或者类欧几里得算法（没学过）。
这个数列可以求出来 $ f_n+\frac{c}{a-1}=a^n(f_0+\frac{c}{a-1}) $ ， $ f_n =a^nf_0+c\cdot \frac{a^n-1}{a-1}=a^nf_0+c\sum_{i=0}^{n-1}a^i $ ，令 $ d = |V_1 - V_2| $ ，则需要求 $ X_d = f_d \mod m $ 的方案数。
令 $ P_n = a^n, s_n = \sum_{i=0}^{n-1}a^i $ ，则 $ X_d \equiv (V_1+V_2)p_d + cs_d \mod m $
由于 $ d $ 固定，令 $ c_1 = p_d, c_2 = cs_d $ ，假设 $ V_1 \ge V_2 $ 则有 $ V_1 = V_2 + d, X_d \equiv (V_2 + d + V_2)c_1 + c_2 \mod m $ ，即 $ X_d \equiv 2c_1V_2 + c_1d+c_2 \mod m $ 是一次函数形式
现在变成了已知 $ x \in [0, t - d] $ 求 $ kx + b \mod m $ 方案数。 $ k=2c_1 $ 为偶数所以在不考虑取模的情况下奇偶性是确定的。 $ m $ 为偶数时，取模后奇偶性不变。
$ m $ 为奇数时，可以通过观察发现，若一个整数 $ y $ 对 $ 2m $ 取模的值在 $ [m,2m−1] $ 范围内，即 $ ⌊y/m⌋ $ 为奇数，则 $ y\mod m $ 与 $ y $ 的奇偶性恰好相反。故只需要计算出 $ kx+b \mod m $ 与 $ kx+b $ 奇偶性相反的次数即可。即只需要求 $ \lfloor \frac{kx+b}{m}\rfloor \bmod 2 = 1 $ 的次数，即 $ x $ 取遍 $ [0,t-d] $ 时 $ \lfloor \frac{kx+b}{m}\rfloor \bmod 2 $ 的和。因为 $ a \bmod b = a-\lfloor \frac{a}{b} \rfloor b $ ，所以需要求 $ \sum_{x=0}^{t-d} \lfloor \frac{kx+b}{m}\rfloor -2\lfloor \frac{kx+b}{2m}\rfloor $ 。发现前后均为 $ \sum_{i=0}^{n} \lfloor \frac{ai+b}{c} \rfloor $ 形式，直接使用类欧几里得
倍增法：
注意到 $ V_1 + V_2 $ 为偶数时， $ |V_1 - V_2| $ 为偶数， $ V_1+V_2 $ 为奇数时， $ |V_1 - V_2| $ 为奇数。可以直接枚举 $ V_1+V_2 $ 取值，倍增记录一下奇偶性信息（求和就行）。
代码：
搜的类欧几里得的代码
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
| #include<bits/stdc++.h>
using namespace std;
#define N 1000010
#define LL long long
int T,t,a,c,m,p[N],s[N];
LL f(LL a,LL b,LL c,LL n)
{
LL m=(a*n+b)/c;
if(!a || !m)return 0;
if(a>=c || b>=c)return n*(n+1)/2*(a/c)+(b/c)*(n+1)+f(a%c,b%c,c,n);
return n*m-f(c,c-b-1,a,m-1);
}
void init()
{
scanf("%d%d%d%d",&t,&a,&c,&m);
p[0]=1;
for(int i=1;i<N;i++){
p[i]=1ll*p[i-1]*a%m;
s[i]=(s[i-1]+p[i-1])%m;
}
LL x=0,y=1ll*(t+1)*(t+1);
for(int d=0;d<=t;d++){
int res=0,k=2ll*p[d],b=(1ll*c*s[d]+1ll*d*p[d])%m;
if(m&1)res=f(k,b,m,t-d)-2ll*f(k,b,2*m,t-d);
if(b&1)res=t-d+1-res;
if(d)res*=2;
x+=res;
}
x=y-x;
LL d=__gcd(x,y);
x/=d,y/=d;
printf("%lld/%lld\n",x,y);
}
int main()
{
scanf("%d",&T);
while(T--)init();
}
|
倍增法
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
| #include <bits/stdc++.h>
#define ll long long
using namespace std;
const ll mod = 1e9 + 7;
const int INF = 0x3f3f3f3f;
const ll INF_LL = 0x3f3f3f3f3f3f3f3f;
const double eqs = 1e-5;
const int maxn = 1e6 + 10;
const int maxm = 1e5 + 10;
int read()
{
int x = 0, flag = 0;
char ch = getchar();
while (ch < '0' || ch > '9')
{
if (ch == '-')
flag = 1;
ch = getchar();
}
while (ch >= '0' && ch <= '9')
{
x = (x << 3) + (x << 1) + (ch ^ 48), ch = getchar();
}
if (flag)
return -x;
return x;
}
int t, n, m, k;
int dp[20][maxn], f[20][maxn], nxt[maxn], a, b;
ll ans = 0;
void cnt(int p, int k)
{
for (int i = 19; i >= 0; i--)
{
if ((1 << i) > k)
continue;
ans += 2ll * dp[i][p];
k -= (1 << i);
p = f[i + 1][p];
}
}
int main()
{
#ifndef ONLINE_JUDGE
#ifdef COMP_DATA
freopen("/mnt/f/文档/课件/ACM比赛/2020hdu多校/第四场/data/E.in", "r", stdin);
freopen("out.txt", "w", stdout);
#else
freopen("in.txt", "r", stdin);
#endif
#endif
t = read();
while (t--)
{
m = read(), a = read(), b = read(), n = read();
ans = 0;
for (int i = 0; i < n; i++)
nxt[i] = (1LL * a * i + b) % n, dp[0][i] = (nxt[i] % 2 == 0), f[0][i] = nxt[i];
ans += m + 1;
for(int i = 1; i < 20; i++)
{
for(int j = 0; j < n; j++)
{
f[i][j] = f[i - 1][f[i - 1][j]];
dp[i][j] = dp[i - 1][j] + dp[i - 1][f[i][j]];
}
}
for (int i = 0; i < 2 * m; i++)
{
if (i <= m)
cnt((i % 2 == 0) ? nxt[i] : i, (i + 1) / 2);
else
cnt((i % 2 == 0) ? nxt[i] : i, (2 * m - i + 1) / 2);
}
ll al = 1ll * (m + 1) * (m + 1);
ll tmp = __gcd(ans, al);
printf("%lld/%lld\n", ans / tmp, al / tmp);
}
return 0;
}
|
E.
题目描述：
数据范围：
题解：
代码：
F.
题目描述：
数据范围：
题解：
代码：
题目描述：
博弈论问题。二维平面 $ n $ 个点， $ Dodo $ 先手移动棋子到任意一个点，距离为 $ d $ ，接下来移动的距离必须大于 $ d $ ，并且没有访问过的点。不能移动时输掉。双方均使用最优策略。
数据范围：
$ 1\le T \le 100 \\ 2 \le n \le 2000 \\ -10^9 \le x,y \le 10^9 $
题解：
博弈论问题，确定必胜或必败策略。发现当一个人选择的是最长边的一个端点，如果另一个人选择另一个端点，就可以获胜。如果把最长边依次选取出来，就可以变成更小的子问题。如果最后只剩下起点 $ 1 $ 一个点，那么不管先手选择哪一个点，后手总可以选择该点所在边的另一个点，使得先手输，否则先手必胜。
题解中给的伪代码：
也可以使用 $ dp[i][j] $ 表示不考虑不能走重复点，当前在 $ i $ ，上一步是 $ j $ 能否获胜。
代码：
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
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
| #include <bits/stdc++.h>
#define ll long long
using namespace std;
const ll mod = 1e9 + 7;
const int INF = 0x3f3f3f3f;
const ll INF_LL = 0x3f3f3f3f3f3f3f3f;
const double eqs = 1e-5;
const int maxn = 2e3 + 10;
const int maxm = 1e5 + 10;
int read()
{
int x = 0, flag = 0;
char ch = getchar();
while (ch < '0' || ch > '9')
{
if (ch == '-')
flag = 1;
ch = getchar();
}
while (ch >= '0' && ch <= '9')
{
x = (x << 3) + (x << 1) + (ch ^ 48), ch = getchar();
}
if (flag)
return -x;
return x;
}
int t, n, m, k;
struct Point
{
int x;
int y;
} point[maxn];
struct Edge
{
ll dis;
int a;
int b;
bool operator<(const Edge &rhs) const
{
return dis > rhs.dis;
}
};
vector<Edge> edge;
ll getDis(Point a, Point b)
{
return 1LL * (a.x - b.x) * (a.x - b.x) + 1LL * (a.y - b.y) * (a.y - b.y);
}
bool vis[maxn];
set<int> st;
int main()
{
#ifndef ONLINE_JUDGE
#ifdef COMP_DATA
freopen("/mnt/f/文档/课件/ACM比赛/2020hdu多校/第四场/data/E.in", "r", stdin);
freopen("out.txt", "w", stdout);
#else
freopen("in.txt", "r", stdin);
#endif
#endif
t = read();
while (t--)
{
n = read();
memset(vis, false, sizeof(vis));
edge.clear();
for (int i = 1; i <= n; i++)
{
point[i] = {read(), read()};
}
for (int i = 1; i <= n; i++)
{
for (int j = i + 1; j <= n; j++)
{
edge.push_back({getDis(point[i], point[j]), i, j});
}
}
sort(edge.begin(), edge.end());
int sum = n;
bool flag = false;
for (int i = 0; i < edge.size(); i++)
{
if (vis[edge[i].a] || vis[edge[i].b])
continue;
ll maxx = edge[i].dis;
st.clear();
int j = i;
while (j < edge.size() && edge[j].dis == maxx)
{
if (vis[edge[j].a] || vis[edge[j].b])
{
j++;
continue;
}
else
{
st.insert(edge[j].a);
st.insert(edge[j].b);
j++;
}
}
i = j - 1;
for(auto it: st)
{
vis[it] = true;
}
if(vis[1] && sum > 1)
{
flag = true;
break;
}
sum -= st.size();
}
if(flag)
{
printf("YES\n");
}
else
{
printf("NO\n");
}
}
return 0;
}
|
H.
题目描述：
数据范围：
题解：
代码：
题目描述：
给出 $ n, x, y $ 构造出一个序列，最长上升子序列长度为 $ x $ ，最长下降则为 $ y $ 。
数据范围：
$ 1\le T \le 100 \\ 1\le n \le 10^5 \\ 1 \le x, y \le n $
题解：
题解中给出了一个定理：
内容：对于一个长度为 $ a \times b + 1 $ 的序列，如果 $ LIS\le a $ ，那么 $ LDS \gt b $ 。
证明：可以使用反证法，假设 $ LIS\le a,LDS \le b $ 。可以发现满足假设条件的最长的序列长度为 $ a \times b $ ，这时直接是一个 $ 1-a\times b $ 的升序序列，每一段长度都为 $ b $ ，然后将每一段反转，得到了一个每段都是 $ LDS = b $ ，共有 $ a $ 段，对整个序列来说 $ LIS=a $ 。
分段讨论 $ n $ 的大小，答案有无
- 如果 $ n \ge a \times b + 1 $ ，这时 $ LIS=a, LDS = b $ ，由定理证明知道这种情况下 $ n $ 最大为 $ a\times b $ ，所以无解
- 如果 $ n \lt a + b - 1 $ ，无解，这时可以弄一个只有一段 $ LIS $ ，一段 $ LDS $ 的序列。
- 可见 $ a + b - 1 \le n \le a \times b $
首先倒序填一个 $ LDS $ ，然后对于前面的分成 $ x-1 $ 个块（总共 $ x $ 个块， $ LDS $ 占用了一下还剩下 $ x-1 $ ），长度 $ \le LDS $ ，将块比较大的放在后面先填了，剩下的比较小的放在前面
代码：
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
| #include <bits/stdc++.h>
#define ll long long
using namespace std;
const ll mod = 1e9 + 7;
const int INF = 0x3f3f3f3f;
const ll INF_LL = 0x3f3f3f3f3f3f3f3f;
const double eqs = 1e-5;
const int maxn = 1e5 + 10;
const int maxm = 1e5 + 10;
int read()
{
int x = 0, flag = 0;
char ch = getchar();
while (ch < '0' || ch > '9')
{
if (ch == '-')
flag = 1;
ch = getchar();
}
while (ch >= '0' && ch <= '9')
{
x = (x << 3) + (x << 1) + (ch ^ 48), ch = getchar();
}
if (flag)
return -x;
return x;
}
int t, n, m, k;
int x, y;
int a[maxn];
int main()
{
#ifndef ONLINE_JUDGE
#ifdef COMP_DATA
freopen("/mnt/f/文档/课件/ACM比赛/2020hdu多校/第四场/data/E.in", "r", stdin);
freopen("out.txt", "w", stdout);
#else
freopen("in.txt", "r", stdin);
freopen("out.txt", "w", stdout);
#endif
#endif
t = read();
while (t--)
{
n = read(), x = read(), y = read();
if( n * 1LL >= 1LL * x * y + 1LL || n < x + y - 1)
{
printf("NO\n");
continue;
}
printf("YES\n");
int cur = n;
for (int i = n - y + 1; i <= n; i++)
{
a[i] = cur--;
}
int index = n - y;
for (int i = x - 1; i >= 1; i--)
{
int len = min(cur - (i - 1), y);
for (int j = index - len + 1; j <= index; j++)
{
a[j] = cur--;
}
index -= len;
}
for(int i = 1; i <= n; i++)
{
printf("%d%c", a[i], " \n"[i==n]);
}
}
return 0;
}
|
题目描述：
二维平面上的点 $ (x,y) $ ，当 $ \gcd(x,y)\gt1 $ 时认为是好点。给出 $ (x_0,y_0) $ 周围的八个点是好点的在 $ s $ 中 $ |s|=z $ 。在该点开始移动，有 $ \frac{1}{z+1} $ 的概率留在原地，有 $ \frac{z}{z+1} $ 的概率移动到 $ s $ 中的一个好点（等概率的）。定义 $ p_t $ 是从 $ (x_0,y_0) $ 出发能够在 $ t $ 步后返回原地的概率。求 $ \lim_{t\to\infty} p_t $
数据范围：
$ 1\le T \le 1000 \\ 2\le x_0, y_0 \le 10^12\\guaranteed \ \gcd(x_0,y_0)\gt 1 $
题解：
Sample Input
Sample Output
拿出老图
这是之前洛谷滑稽机器人那题，打的表可以知道每个连通快还是非常小，可以搜索。看了样例得出了不知道对不对的结论：
- 可以到达对角线的，可以无限延伸为 $ 0/1 $
- 好像输入的都是好点，则答案分子为起点以及周围的好点数，分母为整个连通块的好点数。
题解中也是这样搞的，证明可以查阅相关的资料
有个大佬证明的，我看着像验证的。
代码很容易就可以搞出，但是当时多考虑了输入的坏点。
代码：
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
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
| #include <bits/stdc++.h>
#define ll long long
using namespace std;
const ll mod = 1e9 + 7;
const int INF = 0x3f3f3f3f;
const ll INF_LL = 0x3f3f3f3f3f3f3f3f;
const double eqs = 1e-5;
const int maxn = 1e3 + 10;
const int maxm = 1e5 + 10;
int read()
{
int x = 0, flag = 0;
char ch = getchar();
while (ch < '0' || ch > '9')
{
if (ch == '-')
flag = 1;
ch = getchar();
}
while (ch >= '0' && ch <= '9')
{
x = (x << 3) + (x << 1) + (ch ^ 48), ch = getchar();
}
if (flag)
return -x;
return x;
}
int t, n, m, k;
int nex[10] = {0, 0, 1, 1, 1, 0, -1, -1, -1};
int ney[10] = {0, 1, 1, 0, -1, -1, -1, 0, 1};
ll x, y;
ll gcd(ll a, ll b)
{
return b == 0 ? a : gcd(b, a % b);
}
queue<pair<ll, ll>> q;
map<ll, map<ll, int>> vis;
vector<int> ans;
bool bfs(int &fz, int & fm)
{
while(!q.empty())
q.pop();
ans.clear();
vis.clear();
q.push({x, y});
vis[x][y] = 1;
while(!q.empty())
{
auto out = q.front();
q.pop();
ll nx, ny;
int cnt = 1;
for (int i = 1; i <= 8; i++)
{
nx = out.first + nex[i];
ny = out.second + ney[i];
if(gcd(nx, ny) > 1)
{
cnt++;
if(vis[nx][ny] == 0)
{
if(nx == ny)
return false;
q.push({nx, ny});
vis[nx][ny] = 1;
}
}
}
ans.push_back(cnt);
}
int sum = 0;
for (int i = 0; i < ans.size(); i++)
{
sum += ans[i];
}
fz = ans[0], fm = sum;
int tmp;
tmp = gcd(fz, fm);
if(tmp != 1)
{
fz /= tmp;
fm /= tmp;
}
return true;
}
int main()
{
#ifndef ONLINE_JUDGE
#ifdef COMP_DATA
freopen("/mnt/f/文档/课件/ACM比赛/2020hdu多校/第四场/data/E.in", "r", stdin);
#else
freopen("in.txt", "r", stdin);
#endif
#endif
t = read();
while(t--)
{
scanf("%lld %lld", &x, &y);
if ((x == y) || gcd(x, y) == 1)
{
printf("0/1\n");
}
else
{
int fz, fm;
if(bfs(fz, fm))
{
printf("%d/%d\n", fz, fm);
}
else
{
printf("0/1\n");
}
}
}
return 0;
}
|
题目描述：
给出一个单调栈容量变化过程的序列，有的值可能是 $ -1 $ ，求出有多少中可能的原序列。
数据范围：
$ 1\le T \le 100 \\ 1\le n \le 100 \\ -1\le a_i \le n,a_i \ne 0 \\ \mod 10^9+7 $
题解：
又用到了不会的数据结构——笛卡尔树。
代码：
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
| #include <bits/stdc++.h>
#define ll long long
using namespace std;
const ll mod = 1e9 + 7;
const int INF = 0x3f3f3f3f;
const ll INF_LL = 0x3f3f3f3f3f3f3f3f;
const double eqs = 1e-5;
const int maxn = 1e2 + 10;
const int maxm = 1e5 + 10;
int read()
{
int x = 0, flag = 0;
char ch = getchar();
while (ch < '0' || ch > '9')
{
if (ch == '-')
flag = 1;
ch = getchar();
}
while (ch >= '0' && ch <= '9')
{
x = (x << 3) + (x << 1) + (ch ^ 48), ch = getchar();
}
if (flag)
return -x;
return x;
}
int t, n, m, k;
int a[maxn], c[maxn][maxn], dp[maxn][maxn][maxn];
int main()
{
#ifndef ONLINE_JUDGE
#ifdef COMP_DATA
freopen("/mnt/f/文档/课件/ACM比赛/2020hdu多校/第四场/data/E.in", "r", stdin);
freopen("out.txt", "w", stdout);
#else
freopen("in.txt", "r", stdin);
#endif
#endif
for (int i = 0; i <= maxn - 5; i++)
{
c[i][0] = 1;
for (int j = 1; j <= i; j++)
{
c[i][j] = (c[i - 1][j - 1] + c[i - 1][j]) % mod;
}
}
t = read();
while (t--)
{
n = read();
for (int i = 1; i <= n; i++)
a[i] = read();
memset(dp, 0, sizeof(dp));
for (int i = n; i >= 1; i--)
for (int j = i; j <= n; j++)
for (int k = i; k <= j; k++)
{
int s = ~a[k] ? a[k] : 1;
int end = ~a[k] ? a[k] : n;
for (int p = s; p <= end; p++)
{
dp[i][j][p] = (dp[i][j][p] + 1LL * (i < k ? dp[i][k - 1][p] : 1) * (k < j ? dp[k + 1][j][p + 1] : 1) % mod * c[j - i][k - i]) % mod;
}
}
printf("%d\n", dp[1][n][1]);
}
return 0;
}
|