A - Little Artem and Presents (div2)
1 2 1 2这样加就可以了
#include <bits/stdc++.h> typedef long long ll;
const int N = 1e5 + 5; int main() {
int n; scanf ("%d", &n);
int ans = n / 3 * 2;
if (n % 3) {
ans++;
}
printf ("%d\n", ans);
return 0;
}
B - Little Artem and Grasshopper (div2)
水题,暴力模拟一下
#include <bits/stdc++.h> typedef long long ll;
const int N = 1e5 + 5;
char str[N];
int a[N]; int main() {
int n; scanf ("%d", &n);
scanf ("%s", str);
for (int i=0; i<n; ++i) {
scanf ("%d", a+i);
}
int now = 0;
while (true) {
if (now < 0 || now >= n) {
break;
}
if (a[now] == -1) {
puts ("INFINITE");
return 0;
}
if (str[now] == '>') {
int pre = now;
now = now + a[now];
a[pre] = -1;
} else {
int pre = now;
now = now - a[now];
a[pre] = -1;
}
}
puts ("FINITE");
return 0;
}
构造 C - Little Artem and Matrix (div2)
倒过来做,循环也反着来
#include <bits/stdc++.h> typedef long long ll;
const int N = 1e2 + 5;
const int Q = 1e4 + 5;
int a[N][N];
int t[Q], row[Q], col[Q], x[Q]; int main() {
int n, m, q; scanf ("%d%d%d", &n, &m, &q);
for (int i=1; i<=q; ++i) {
scanf ("%d", t+i);
if (t[i] == 1) {
scanf ("%d", row+i);
}
if (t[i] == 2) {
scanf ("%d", col+i);
}
if (t[i] == 3) {
scanf ("%d%d%d", row+i, col+i, x+i);
}
//printf ("%d %d %d %d\n", t[i], row[i], col[i], x[i]);
}
for (int i=q; i>=1; --i) {
if (t[i] == 1) {
int last = a[row[i]][m];
for (int j=m; j>=2; --j) {
a[row[i]][j] = a[row[i]][j-1];
}
a[row[i]][1] = last;
}
if (t[i] == 2) {
int last = a[n][col[i]];
for (int j=n; j>=2; --j) {
a[j][col[i]] = a[j-1][col[i]];
}
a[1][col[i]] = last;
}
if (t[i] == 3) {
a[row[i]][col[i]] = x[i];
}
}
for (int i=1; i<=n; ++i) {
for (int j=1; j<=m; ++j) {
printf ("%d%c", a[i][j], j == m ? '\n' : ' ');
}
}
return 0;
}
数学 D - Little Artem and Dance (div2)
题意:男生与女生围成圈跳舞,女生的位置不变,男生可以移动x个女生或者相邻的男生奇偶互换,问最后男生的排列
分析:问题的关键点在于奇数男生的圈顺序不变,偶数也不变,只是起点的位置改变,所以只要对两个起点操作就行了。
#include <bits/stdc++.h> typedef long long ll;
const int N = 1e6 + 5;
int ans[N]; int main() {
int p0 = 0, p1 = 1;
int n, q; scanf ("%d%d", &n, &q);
for (int i=0; i<q; ++i) {
int type; scanf ("%d", &type);
if (type == 1) {
int x; scanf ("%d", &x);
p0 = (p0 + x + n) % n;
p1 = (p1 + x + n) % n;
} else {
p0 = p0 ^ 1;
p1 = p1 ^ 1;
}
}
for (int i=0; i<n; i+=2) {
ans[(p0+i)%n] = i + 1;
}
for (int i=1; i<n; i+=2) {
ans[(p1+i-1)%n] = i + 1;
}
for (int i=0; i<n; ++i) {
printf ("%d%c", ans[i], i == n-1 ? '\n' : ' ');
}
return 0;
}
数学+前(后)缀 C - Little Artem and Random Variable (div1)
题意:已知p(max(a,b)=k) 和 p(min(a,b)=k)的概率,求p(a=k) 和 p(b=k)
分析:
P(a = k) = P(a <= k) — P(a <= k-1) P(max(a, b) <= k) = P(a <= k) * P(b <= k)
P(min(a, b) >= k) = P(a >= k) * P(b >= k) = (1 — P(a <= k-1)) *(1 — P(b <= k-1))
即
解方程的和,从而求得和
#include <bits/stdc++.h> const int N = 1e5 + 5;
double p[N], q[N], a[N], b[N]; int main() {
int n; scanf ("%d", &n);
for (int i=1; i<=n; ++i) {
scanf ("%lf", p+i);
p[i] += p[i-1];
}
for (int i=1; i<=n; ++i) {
scanf ("%lf", q+i);
}
for (int i=n; i>=1; --i) {
q[i] += q[i+1];
}
for (int i=1; i<=n; ++i) {
double A = p[i], B = q[i+1];
double C = B - A - 1;
double delta = sqrt (std::max (C*C - 4 * A, 0.0));
a[i] = (-C+delta) / 2;
b[i] = (-C-delta) / 2;
}
for (int i=1; i<=n; ++i) {
printf ("%.10f%c", a[i] - a[i-1], i == n ? '\n' : ' ');
}
for (int i=1; i<=n; ++i) {
printf ("%.10f%c", b[i] - b[i-1], i == n ? '\n' : ' ');
}
return 0;
}