The 2014 ACM-ICPC Asia Mudanjiang Regional First Round
7582 ワード
The 2014 ACM-ICPC Asia Mudanjiang Regional First Round
タイトルリンク
最初のネット試合はまあまあだった.のA,B,C,H,Jを5題やった
A:問題にサインして、探してみればいいです.
B:构造问题ですが、私の构造方法はこうです.まず第一列を満タンにして、それから第二列から半分にして、毎回1长を曲がって敷いて、このように缲り返してはいけないことを保证して、それから半分后に2长を曲がって敷いて、それから最后に1つの空席が残って、ちょうど1つ置くことができて、この曲がった长さは(n+1)/2で、最初はwaを返してなぜか分かりませんが、もとはn=6の時、最後の1枚と2の長さの1枚が繰り返して、そこで手動で6個を構成して過ぎました
C:dfs、まずlH:欲張り、dfs、数位dpのような方法でdfs欲張り構造列を作って、毎回前に数字を置いて、後ろにもいくつかの数字を置いて、枝を切って、今置いている上位がすでに探した答えより小さいならば、探す必要はありません
J:この問題も水の問題です.文字列の長さが大きくないので、暴力的にやればいいです.
コード:
A:
B:
C:
H:
J:
タイトルリンク
最初のネット試合はまあまあだった.のA,B,C,H,Jを5題やった
A:問題にサインして、探してみればいいです.
B:构造问题ですが、私の构造方法はこうです.まず第一列を満タンにして、それから第二列から半分にして、毎回1长を曲がって敷いて、このように缲り返してはいけないことを保证して、それから半分后に2长を曲がって敷いて、それから最后に1つの空席が残って、ちょうど1つ置くことができて、この曲がった长さは(n+1)/2で、最初はwaを返してなぜか分かりませんが、もとはn=6の時、最後の1枚と2の長さの1枚が繰り返して、そこで手動で6個を構成して過ぎました
C:dfs、まずl
J:この問題も水の問題です.文字列の長さが大きくないので、暴力的にやればいいです.
コード:
A:
#include <cstdio>
#include <cstring>
const int N = 55;
int t, n, H[N], ans;
int main() {
scanf("%d", &t);
while (t--) {
scanf("%d", &n);
for (int i = 1; i <= n; i++)
scanf("%d", &H[i]);
ans = 0;
for (int i = 2; i <= n - 1; i++) {
if (H[i] > H[i - 1] && H[i] > H[i + 1])
ans++;
}
printf("%d
", ans);
}
return 0;
}B:
#include <cstdio>
#include <cstring>
const int N = 105;
int t, n;
char g[N][N];
char col[2];
void solve() {
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++) {
g[i][j] = 'B';
}
for (int i = 0; i < n; i++)
g[0][i] = 'Y';
for (int i = 0; i < (n - 1) / 2; i++) {
char c = col[i % 2];
for (int j = i + 1; j < n; j++)
g[j][i] = c;
for (int j = 1; j <= i + 1; j++)
g[j][i + 1] = c;
}
for (int i = (n - 1) / 2; i < n - 1; i++) {
char c = col[i % 2];
for (int j = i + 2; j < n; j++)
g[j][i] = c;
g[i + 2][i + 1] = c;
for (int j = 2; j <= i + 2; j++)
g[j][i + 2] = c;
}
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++)
printf("%c", g[i][j]);
printf("
");
}
}
int main() {
col[0] = 'G';
col[1] = 'R';
scanf("%d", &t);
while (t--) {
scanf("%d", &n);
if (n == 1) printf("Y
");
else if (n <= 4) printf("No solution!
");
else if (n == 6) {
printf("YYYYYY
");
printf("GGRGRR
");
printf("GRRGRB
");
printf("GRGGRB
");
printf("GRGRRB
");
printf("GRGBBB
");
}
else {
solve();
}
}
return 0;
}C:
#include <cstdio>
#include <cstring>
#include <vector>
#include <algorithm>
using namespace std;
const int N = 100005;
int t, n, m, l, k, s[N];
bool vis[N], isch[N];
vector<int> g[N];
int dfs2(int u) {
vis[u] = true;
int ans = 1;
for (int i = 0; i < g[u].size(); i++) {
int v = g[u][i];
if (vis[v]) continue;
ans += dfs2(v);
}
return ans;
}
void dfs(int u) {
vis[u] = true;
if (isch[u]) {
isch[u] = false;
return;
}
for (int i = 0; i < g[u].size(); i++) {
int v = g[u][i];
if (vis[v]) continue;
dfs(v);
}
}
bool solve() {
if (l < k) return false;
if (dfs2(1) != n) return false;
memset(vis, false, sizeof(vis));
isch[s[0]] = false;
for (int i = 0; i < l; i++) {
if (isch[s[i]]) return false;
dfs(s[i]);
}
return true;
}
int main() {
scanf("%d", &t);
while (t--) {
scanf("%d%d%d", &n, &m, &k);
for (int i = 1; i <= n; i++)
g[i].clear();
int tmp;
memset(vis, false, sizeof(vis));
memset(isch, false, sizeof(isch));
for (int i = 0; i < k; i++) {
scanf("%d", &tmp);
isch[tmp] = true;
}
int u, v;
for (int i = 0; i < m; i++) {
scanf("%d%d", &u, &v);
g[u].push_back(v);
g[v].push_back(u);
}
scanf("%d", &l);
for (int i = 0; i < l; i++)
scanf("%d", &s[i]);
printf("%s
", solve() ? "Yes" : "No");
}
return 0;
}H:
#include <cstdio>
#include <cstring>
char A[35];
int t, n, num[35], ans[35];
bool judge(int s) {
for (int i = 0; i <= s; i++) {
if (ans[i] > num[i]) return false;
else if (ans[i] < num[i]) return true;
}
return true;
}
bool check() {
for (int i = 0; i < n; i++) {
if (num[i] > ans[i])
return true;
else if (num[i] < ans[i]) return false;
}
return false;
}
void dfs(int s, int e, int flag1, int flag2, int flag3) {
if (s > e) {
if (flag1 == 0 && flag2) return;
if (check()) {
for (int i = 0; i < n; i++)
ans[i] = num[i];
}
return;
}
int end = A[s] - '0';
if (flag1) end = 9;
for (int i = end; i >= 0; i--) {
if (flag1 == 0 && i < end) flag1 = 1;
if (!flag3 && i == 0) continue;
num[s] = i;
if (!judge(s)) break;
if (e != n - 1 && num[e + 1] == i)
dfs(s + 1, e, flag1, flag2, 1);
for (int j = e; j >= s; j--) {
num[j] = i;
if (num[j] > A[j] - '0') flag2 = 1;
if (num[j] < A[j] - '0') flag2 = 0;
dfs(s + 1, j - 1, flag1, flag2, 1);
}
}
if (!judge(s)) return;
if (!flag3) {
num[s] = 0;
dfs(s + 1, e, flag1, flag2, flag3);
}
}
int main() {
scanf("%d", &t);
while (t--) {
scanf("%s", A);
n = strlen(A);
for (int i = 0; i < n; i++)
ans[i] = 0;
dfs(0, n - 1, 0, 1, 0);
int s = 0;
while (s < n - 1 && ans[s] == 0) {s++;}
for (int i = s; i < n; i++)
printf("%d", ans[i]);
printf("
");
}
return 0;
}J:
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <string>
#include <algorithm>
#include <iostream>
using namespace std;
int t;
string str;
void handle() {
string tmp = "";
for (int i = 0; i < str.length(); i++)
if ((str[i] >= 'a' && str[i] <= 'z') || (str[i] >= 'A' && str[i] <= 'Z')) {
tmp += str[i];
}
str = tmp;
}
int n;
bool solve1() {
for (int i = 0; i < n; i++) {
string A = "";
for (int j = 0; j <= i; j++)
A += str[j];
int bl = n - (i + 1) * 3;
if (bl <= 0 || bl % 2) continue;
string B = "";
for (int j = i + 1; j < i + 1 + bl / 2; j++)
B += str[j];
if (A != B && A + B + A + B + A == str) return true;
}
return false;
}
bool judge(string AB, string C) {
for (int i = 0; i < AB.length(); i++) {
string A = "", B = "";
for (int j = 0; j <= i; j++)
A += AB[j];
for (int j = i + 1; j < AB.length(); j++)
B += AB[j];
if (A == "" || B == "" || C == "") continue;
if (A == B || A == C || C == B) continue;
return true;
}
return false;
}
bool solve2() {
for (int i = 0; i < n; i++) {
string AB = "";
for (int j = 0; j <= i; j++)
AB += str[j];
int cl = n - (i + 1) * 3;
if (cl <= 0) continue;
string C = "";
for (int j = 2 * i + 2; j < 2 * i + 2 + cl; j++)
C += str[j];
if (judge(AB, C) && AB + AB + C + AB == str) return true;
}
return false;
}
int main() {
scanf("%d%*c", &t);
while (t--) {
getline(cin, str);
handle();
n = str.length();
if (solve1() || solve2()) printf("Yes
");
else printf("No
");
}
return 0;
}