Problems # Name A inna and choose options standard input/output 1 s, 256 MB x1942 B Inna and New Matrix of Candies standard input/output 1 s, 256 MB x1556 C Inna and Huge Candy Matrix standard input/output 2 s, 256 MB x1114 D Dima and Bact
Problems
| # | Name | ||
|---|---|---|---|
| A |
inna and choose options
standard input/output 1 s, 256 MB |
 
|
 x1942 |
| B |
Inna and New Matrix of Candies
standard input/output 1 s, 256 MB |
|
x1556 |
| C |
Inna and Huge Candy Matrix
standard input/output 2 s, 256 MB |
|
x1114 |
| D |
Dima and Bacteria
standard input/output 2 s, 256 MB |
|
x371 |
| E |
Inna and Binary Logic
standard input/output 3 s, 256 MB |
|
x169 |
A题：直接暴力枚举每种情况即可。水题
B题：记录下S，G的距离，每种距离只要一次，开个vis数组标记，最后遍历一遍看又几个即可
C题：模拟旋转即可。
D题：并查集+floyd，把w=0的边的点并查集处理，判断同种类是否都在一个集合内，不是就No，剩下的就利用floyd求出最短路即可。
E题：位运算，每个数字对应的每个位向左和向右延生，这个区间内向下的那个三角形区间一定是会增加(1
代码：
A题：
#include <stdio.h>
#include <string.h>
int t, n;
char str[15];
char save[15][15];
bool judge(int a, int b) {
int i, j;
for (i = 0; i < a; i++) {
for (j = 0; j < b; j++)
save[i][j] = str[i * b + j];
}
for (i = 0; i < b; i++) {
for (j = 0; j < a; j++) {
if (save[j][i] != 'X') break;
}
if (j == a) return true;
}
return false;
}
int main() {
scanf("%d", &t);
while (t--) {
scanf("%s", str);
int ans = 0;
if (judge(1, 12)) ans++;
if (judge(2, 6)) ans++;
if (judge(3, 4)) ans++;
if (judge(4, 3)) ans++;
if (judge(6, 2)) ans++;
if (judge(12, 1)) ans++;
printf("%d", ans);
if (judge(1, 12)) printf(" 1x12");
if (judge(2, 6)) printf(" 2x6");
if (judge(3, 4)) printf(" 3x4");
if (judge(4, 3)) printf(" 4x3");
if (judge(6, 2)) printf(" 6x2");
if (judge(12, 1)) printf(" 12x1");
printf("\n");
}
return 0;
}B题：
#include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std;
const int N = 1005;
int n, m, i, j, vis[N];
char g[N][N];
int main() {
scanf("%d%d", &n, &m);
for (i = 0; i < n; i++)
scanf("%s", g[i]);
for (i = 0; i < n; i++) {
int G, S;
for (j = 0; j < m; j++) {
if (g[i][j] == 'G') G = j;
if (g[i][j] == 'S') S = j;
}
if (S < G) {
printf("-1\n");
return 0;
}
int d = S - G;
vis[d] = 1;
}
int ans = 0;
for (int i = 0; i <= 1000; i++)
if (vis[i]) ans++;
printf("%d\n", ans);
return 0;
}C题：
#include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std;
int n, m, x, y, z, p, i, j;
struct Point {
int x, y;
} po[100005];
void at(Point &a) {
int x = a.x, y = a.y;
a.y = n - x + 1;
a.x = y;
}
void ht(Point &a) {
int x = a.x, y = a.y;
a.y = m - y + 1;
a.x = x;
}
void ct(Point &a) {
int x = a.x, y = a.y;
a.y = x;
a.x = m - y + 1;
}
int main() {
scanf("%d%d%d%d%d%d", &n, &m, &x, &y, &z, &p);
x %= 4;
y %= 2;
z %= 4;
for (i = 0; i < p; i++)
scanf("%d%d", &po[i].x, &po[i].y);
for (j = 0; j < x; j++) {
for (i = 0; i < p; i++) {
at(po[i]);
}
int t = n; n = m; m = t;
}
for (j = 0; j < y; j++) {
for (i = 0; i < p; i++) {
ht(po[i]);
}
}
for (j = 0; j < z; j++) {
for (i = 0; i < p; i++) {
ct(po[i]);
}
int t = n; n = m; m = t;
}
for (i = 0; i < p; i++)
printf("%d %d\n", po[i].x, po[i].y);
return 0;
}D题：
#include <stdio.h>
#include <string.h>
#include <vector>
#define INF 0x3f3f3f3f
#define min(a,b) ((a)<(b)?(a):(b))
const int N = 100005;
int n, m, K, type[N], i, j, k;
int f[505][505], fa[N], c[505];
int find(int x) {
if (x == fa[x])
return x;
x = find(fa[x]);
}
int main() {
scanf("%d%d%d", &n, &m, &K);
int tn = 0;
memset(f, INF, sizeof(f));
for (i = 1; i <= n; i++)
fa[i] = i;
for (i = 1; i <= K; i++) {
f[i][i] = 0;
scanf("%d", &c[i]);
for (j = 0; j < c[i]; j++) {
type[++tn] = i;
}
}
int u, v, w;
while (m--) {
scanf("%d%d%d", &u, &v, &w);
if (type[u] != type[v] && f[type[u]][type[v]] > w) {
f[type[u]][type[v]] = w;
f[type[v]][type[u]] = w;
}
if (w == 0) {
int pu = find(u);
int pv = find(v);
if (pu != pv)
fa[pv] = pu;
}
}
for (i = 2; i <= n; i++) {
int u = i - 1, v = i;
if (type[u] == type[v]) {
if (find(u) != find(v)) {
printf("No\n");
return 0;
}
}
}
printf("Yes\n");
for (k = 1; k <= K; k++) {
for (i = 1; i <= K; i++) {
for (j = 1; j <= K; j++) {
f[i][j] = min(f[i][j], f[i][k] + f[k][j]);
}
}
}
for (i = 1; i <= K; i++) {
for (j = 1; j < K; j++) {
if (f[i][j] == INF) f[i][j] = -1;
printf("%d ", f[i][j]);
}
if (f[i][K] == INF) f[i][K] = -1;
printf("%d\n", f[i][K]);
}
return 0;
}E题：
#include <stdio.h>
#include <string.h>
const int N = 100005;
const int M = 20;
int n, m, i, j, b;
int a[N][M];
__int64 sum, mi[32];
int main() {
mi[0] = 1;
for (i = 1; i < 32; i++)
mi[i] = mi[i - 1] * 2;
sum = 0;
scanf("%d%d", &n, &m);
int num;
for (i = 1; i <= n; i++) {
scanf("%d", &num);
for (b = 0; b <= 18; b++) {
if (num&mi[b]) {
a[i][b] = 1;
}
}
}
__int64 k = 0;
for (b = 0; b <= 18; b++) {
for (i = 1; i <= n; i++) {
if (a[i][b]) k++;
else {
sum += mi[b] * k * (k + 1) / 2;
k = 0;
}
}
if (k != 0) {
sum += mi[b] * k * (k + 1) / 2;
k = 0;
}
}
int p;
__int64 v;
while (m--) {
scanf("%d%I64d", &p, &v);
__int64 ans1 = 0, ans2 = 0;
for (b = 0; b <= 18; b++) {
if (a[p][b]) sum -= mi[b];
if (a[p][b] && (v&mi[b]) == 0) {
__int64 l = p, r = p;
while (a[l - 1][b]) {
l--;
}
while (a[r + 1][b]) {
r++;
}
ans1 += mi[b] * ((p - l) * (r - p) + (p - l) + (r - p));
a[p][b] = 0;
}
else if ((v&mi[b]) && a[p][b] == 0) {
int l = p, r = p;
while (a[l - 1][b]) {
l--;
}
while (a[r + 1][b]) {
r++;
}
ans2 += mi[b] * ((p - l) * (r - p) + (p - l) + (r - p));
a[p][b] = 1;
}
}
sum = sum - ans1 + ans2 + v;
printf("%I64d\n", sum);
}
return 0;
}
