构造题，可以考虑寻找小于等于每个数的最大的2的次幂作为该数的周期。将最大的周期定为 m m m 。然后从小到大排序，依次将每个下标按周期填入。剩余的空白位置可以随意填一些1到n的数。
code#includeB B B:Eezie and Pieusing namespace std; using ll = long long; const int N = 1e6 + 10; const int M = 2e5 + 10; ll n, m, a[N]; struct node { ll t; int x; bool operator<(const node &b) const { return t < b.t; } }f[M]; void slove() { cin >> n; m = 0; for (int i = 1; i <= n; i++) { int x; cin >> x; a[i] = x; ll cnt = 0, base = 2; while (base <= x) { cnt++; base <<= 1; } f[i].t = (1 << cnt); if (f[i].t > m) m = f[i].t; f[i].x = i; } sort(f + 1, f + 1 + n); m = f[n].t; cout << m << endl; vector ans(m, 0); for (int i = 1, st = 0; i <= n; i++) { while (st < m && ans[st]) st++; assert(st != m); int l = f[i].t; for (int j = st; j < m; j += l) ans[j] = f[i].x; } for (int i = 0; i < m; i++) { if (ans[i] == 0) ans[i] = 1; } for (int i = 0; i < m; i++) cout << ans[i] << " n"[i == m - 1]; } int main() { cin.tie(0)->sync_with_stdio(0); slove(); return (0^0); }
队友写的，还没看（
G G G: Icon Design 思路傻逼模拟题，就是按照要求画出对应长度的logo，暴力for循环
#includeI I I:Lineusing namespace std; int n; void slove() { cin >> n; for (int i = 1; i <= 13 * n + 19; i++) cout << '*'; cout << endl; for (int j = 1; j <= n; j++) { cout << '*'; for (int i = 2; i < 13 * n + 19; i++) cout << '.'; cout << "*n"; } for (int j = 1; j <= 2 * n + 3; j++) { cout << '*'; for (int i = 1; i <= n + 1; i++) cout << '.'; cout << '@'; for (int i = 2; i <= 2 * n + 2; i++) { if (i == j) cout << '@'; else cout << '.'; } cout << '@'; for (int i = 1; i <= n + 1; i++) cout << '.'; cout << '@'; if (j == 1 || j == n + 2) for (int i = 1; i <= 2 * n + 2; i++) cout << '@'; else for (int i = 1; i <= 2 * n + 2; i++) cout << '.'; for (int i = 1; i <= n + 1; i++) cout << '.'; cout << '@'; if (j == 2 * n + 3) for (int i = 1; i <= 2 * n + 2; i++) cout << '@'; else for (int i = 1; i <= 2 * n + 2; i++) cout << '.'; for (int i = 1; i <= n + 1; i++) cout << '.'; if (j == 1 || j == n + 2 || j == 2 * n + 3) { for (int i = 1; i <= 2 * n + 3; i++) cout << '@'; } else if (j <= n + 1) { cout << '@'; for (int i = 1; i <= 2 * n + 2; i++) cout << '.'; } else { for (int i = 1; i <= 2 * n + 2; i++) cout << '.'; cout << '@'; } for (int i = 1; i <= n + 1; i++) cout << '.'; cout << "*n"; } for (int j = 1; j <= n; j++) { cout << '*'; for (int i = 2; i < 13 * n + 19; i++) cout << '.'; cout << "*n"; } for (int i = 1; i <= 13 * n + 19; i++) cout << '*'; cout << endl; } int main() { cin.tie(0)->sync_with_stdio(0); slove(); return 0; }
待补。。。
J J J:Number Game 思路推柿子。首先判断 x == c 是否成立。如果不成立，则需要考虑前面的因素。
可以发现存在两种情况。
一是先执行 B-C 再执行 A-B，然后进行循环。可以得到两个方程通式。
(
2
n
−
1
)
B
−
(
n
−
1
)
A
−
C
=
x
n
A
−
2
n
B
+
C
=
x
(2n - 1)B - (n - 1)A - C = x\ nA - 2nB + C = x
(2n−1)B−(n−1)A−C=xnA−2nB+C=x
二是先执行 A-B 再执行 B-C，然后进行循环。可以得到两个方程通式。
n
A
−
(
2
n
−
1
)
B
−
C
=
x
2
n
B
−
n
A
+
C
=
x
nA - (2n - 1)B - C = x\ 2nB - nA + C = x
nA−(2n−1)B−C=x2nB−nA+C=x
分别判断以上这四种情况下 n n n 的值是否为大于零的整数，如果不是则无法构成相关的 x x x 。
code#includeM M M:Z-Game on grid 思路using namespace std; using ll = long long; void slove() { ll a, b, c, t; cin >> a >> b >> c >> t; if (t == c) return cout << "Yesn", void(); ll x[4], y[4]; x[0] = b * 2 - a; x[1] = -x[0]; x[2] = x[0]; x[3] = -x[0]; y[0] = t - a + b + c; y[1] = t - c; y[2] = t - c; y[3] = t - b + c; for (int i = 0; i < 4; i++) { if (x[i] == 0) { // x[i] = 0的情况要特判 if (y[i] == 0) return cout << "Yesn", void(); else continue; } if (y[i] % x[i] == 0) { ll k = y[i] / x[i]; if (k >= 1) return cout << "Yesn", void(); } } cout << "Non"; } int main() { cin.tie(0)->sync_with_stdio(0); int _; cin >> _; while (_--) { slove(); } return (0^0); }
考虑从后往前dp,
d
p
i
,
j
,
0
/
1
/
2
dp_{i, j, 0/1/2}
dpi,j,0/1/2 分别为到达
(
i
,
j
)
(i, j)
(i,j) 点时是否一定会赢，平局或输这三种情况，当
d
p
i
,
j
,
0
/
1
/
2
=
1
dp_{i, j, 0/1/2} = 1
dpi,j,0/1/2=1 则可以，否则不行。状态转移的时候分别考虑Alice和Bob的选择，如果Alice希望最终达到赢的情况，则Bob始终希望往相反的方向考虑。则有状态转移方程如下
d
p
i
,
j
,
k
=
{
d
p
i
+
1
,
j
,
k
∣
d
p
i
,
j
+
1
,
k
,
if
i
+
j
is even
d
p
i
+
1
,
j
,
k
&
d
p
i
,
j
+
1
,
k
,
if
i
+
j
is odd
dp_{i, j, k} = begin{cases} dp_{i + 1, j, k} | dp_{i, j + 1, k}, & text{if }i + jtext{ is even} \ dp_{i + 1, j, k} & dp_{i, j + 1, k}, & text{if }i + jtext{ is odd} end{cases}
dpi,j,k={dpi+1,j,k∣dpi,j+1,k,dpi+1,j,k&dpi,j+1,k,if i+j is evenif i+j is odd
需要特殊注意边界条件。
#includeusing namespace std; using ll = long long; const int N = 510; int n, m; string s[N]; int dp[N][N][3]; inline void print(int x) { if (x == 1) cout << "yes "; else cout << "no "; } void slove() { cin >> n >> m; for (int i = 0; i < n; i++) cin >> s[i]; for (int i = 0; i <= n; i++) for (int j = 0; j <= m; j++) for (int k = 0; k < 3; k++) dp[i][j][k] = 0; char c = s[n - 1][m - 1]; if (c == 'A') dp[n - 1][m - 1][0] = 1; if (c == '.') dp[n - 1][m - 1][1] = 1; if (c == 'B') dp[n - 1][m - 1][2] = 1; for (int i = n - 1; i >= 0; i--) for (int j = m - 1; j >= 0; j--) { if (i == n - 1 and j == m - 1) continue; if (s[i][j] == 'A') dp[i][j][0] = 1; else if (s[i][j] == 'B') dp[i][j][2] = 1; else { if (i == n - 1) for (int k = 0; k < 3; k++) dp[i][j][k] = dp[i][j + 1][k]; else if (j == m - 1) for (int k = 0; k < 3; k++) dp[i][j][k] = dp[i + 1][j][k]; else for (int k = 0; k < 3; k++) if ((i + j) % 2 == 0) dp[i][j][k] = (dp[i + 1][j][k] | dp[i][j + 1][k]); else dp[i][j][k] = (dp[i + 1][j][k] & dp[i][j + 1][k]); } } for (int k = 0; k < 3; k++) print(dp[0][0][k]); cout << 'n'; } int main() { cin.tie(0)->sync_with_stdio(0); int _; cin >> _; while (_--) { slove(); } return (0^0); }
