首页 > 代码库 > The 2014 ACM-ICPC Asia Mudanjiang Regional First Round
The 2014 ACM-ICPC Asia Mudanjiang Regional First Round
The 2014 ACM-ICPC Asia Mudanjiang Regional First Round
题目链接
第一场网络赛打得还不错。。搞了5题
A，B，C，H，J
A：就一个签到题，找一遍即可
B：构造问题，我的构造方法是这样的，先铺满第一排，然后从第二排开始到一半，就每次拐1长度去铺，这样保证都不出重复，然后一半之后用拐2长度的的去铺，然后最后会剩下一个空位，正好能放下一个，这个拐的长度为(n + 1) / 2，一开始还wa了不知道为什么，原来是n = 6的时候，最后一块和拐2长度的一块会重复，于是手动构造个6个就过了
C：dfs，首先l < k就是错误，不连通就是错误，从每个侦探器进去dfs，每次搜到其他侦探器就停下，并把侦探器标记清空，走过的点就标记掉无须走第二次，然后如果有一个侦探器（第一个除外）进入的时候没被清空，就是错误
H：贪心，dfs，用类似数位dp的方法去dfs贪心构造串，每次前面放一个数字，后面也跟着放一些数字，要加个剪枝，就是如果当前放的前几位比已经找过的答案要小，那就没必要搜下去了
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\n", 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("\n");
}
}
int main() {
col[0] = 'G';
col[1] = 'R';
scanf("%d", &t);
while (t--) {
scanf("%d", &n);
if (n == 1) printf("Y\n");
else if (n <= 4) printf("No solution!\n");
else if (n == 6) {
printf("YYYYYY\n");
printf("GGRGRR\n");
printf("GRRGRB\n");
printf("GRGGRB\n");
printf("GRGRRB\n");
printf("GRGBBB\n");
}
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\n", 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("\n");
}
return 0;
}#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\n");
else printf("No\n");
}
return 0;
}The 2014 ACM-ICPC Asia Mudanjiang Regional First Round
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。