![[CCF2015.12]题解](https://image.shishitao.com:8440/aHR0cHM6Ly9ia3FzaW1nLmlrYWZhbi5jb20vdXBsb2FkL2NoYXRncHQtcy5wbmc%2FIQ%3D%3D.png?!?w=700&webp=1 "[CCF2015.12]题解")
201512-1 数位之和
水题一个，取模除以10胡搞即可（不知道字符串为什么不行
#include <algorithm>
#include <iostream>
#include <iomanip>
#include <cstring>
#include <climits>
#include <complex>
#include <fstream>
#include <cassert>
#include <cstdio>
#include <bitset>
#include <vector>
#include <deque>
#include <queue>
#include <stack>
#include <ctime>
#include <set>
#include <map>
#include <cmath> using namespace std; int n; int main() {
while(~scanf("%d", &n)) {
int ans = ;
while(n) {
ans += n % ;
n /= ;
}
printf("%d\n", ans);
}
return ;
}
1
201512-2 消除类游戏
按行按列枚举三个相邻的中点，看看左右是否和它相同颜色，如果相同就打标记，最后根据标记处理所有点。
#include <algorithm>
#include <iostream>
#include <iomanip>
#include <cstring>
#include <climits>
#include <complex>
#include <fstream>
#include <cassert>
#include <cstdio>
#include <bitset>
#include <vector>
#include <deque>
#include <queue>
#include <stack>
#include <ctime>
#include <set>
#include <map>
#include <cmath> using namespace std; const int maxn = ;
const int dx[] = {, , -, };
const int dy[] = {, -, , };
int n, m;
int G[maxn][maxn];
bool dis[maxn][maxn]; bool ok(int i, int j) {
return i >= && j >= && i < n && j < m;
} int main() {
// freopen("in", "r", stdin);
while(~scanf("%d %d", &n, &m)) {
memset(dis, , sizeof(dis));
for(int i = ; i < n; i++) {
for(int j = ; j < m; j++) {
scanf("%d", &G[i][j]);
}
}
for(int i = ; i < n; i++) {
for(int j = ; j < m; j++) {
if(ok(i-, j) && ok(i+, j)) {
if(G[i-][j] == G[i+][j] && G[i-][j] == G[i][j] && G[i+][j] == G[i][j]) {
dis[i-][j] = dis[i+][j] = dis[i][j] = ;
}
}
}
}
for(int i = ; i < n; i++) {
for(int j = ; j < m; j++) {
if(ok(i, j-) && ok(i, j+)) {
if(G[i][j-] == G[i][j+] && G[i][j-] == G[i][j] && G[i][j+] == G[i][j]) {
dis[i][j-] = dis[i][j+] = dis[i][j] = ;
}
}
}
}
for(int i = ; i < n; i++) {
for(int j = ; j < m; j++) {
if(dis[i][j]) G[i][j] = ;
printf("%d ", G[i][j]);
}
printf("\n");
}
}
return ;
}
2
201512-3 画图
小模拟，注意好行和列即可，第一个样例提供了一个trick，那就是覆盖后的颜色还可以被继续覆盖，并且覆盖后可以在其上画线段。判断线段相交在每画一段的时候完成，假如画之前存在与它不一样方向的线段就变+（注意原本就是+的情况）。填充操作一遍dfs就行，和POJ的一个题一样。
#include <algorithm>
#include <iostream>
#include <iomanip>
#include <cstring>
#include <climits>
#include <complex>
#include <fstream>
#include <cassert>
#include <cstdio>
#include <bitset>
#include <vector>
#include <deque>
#include <queue>
#include <stack>
#include <ctime>
#include <set>
#include <map>
#include <cmath> using namespace std; typedef struct Point {
int x, y;
Point() {}
Point(int xx, int yy) : x(xx), y(yy) {}
}Point; const int maxn = ;
const int dx[] = {, , , -};
const int dy[] = {, -, , }; char G[maxn][maxn];
int n, m, q;
Point a, b;
int cmd; void init() {
memset(G, , sizeof(G));
for(int i = ; i < n; i++) {
for(int j = ; j < m; j++) {
G[i][j] = '.';
}
}
} void line(Point a, Point b) {
if(a.y == b.y) {
if(a.x > b.x) {
Point tmp = a;
a = b;
b = tmp;
}
for(int i = a.x; i <= b.x; i++) {
if(G[i][a.y] == '-' || G[i][a.y] == '+') G[i][a.y] = '+';
else G[i][a.y] = '|';
}
}
else if(a.x == b.x) {
if(a.y > b.y) {
Point tmp = a;
a = b;
b = tmp;
}
for(int i = a.y; i <= b.y; i++) {
if(G[a.x][i] == '|' || G[a.x][i] == '+') G[a.x][i] = '+';
else G[a.x][i] = '-';
}
}
}
bool ok(int i, int j) {
return i >= && j >= && i < n && j < m;
} void dfs(int x, int y, char s) {
for(int i = ; i < ; i++) {
int xx = x + dx[i];
int yy = y + dy[i];
if(ok(xx, yy) && !(G[xx][yy] == '|' || G[xx][yy] == '+' || G[xx][yy] == '-' ) && G[xx][yy] != s) {
G[xx][yy] = s;
dfs(xx, yy, s);
}
}
} int main() {
// freopen("in", "r", stdin);
while(~scanf("%d %d", &m, &n)) {
scanf("%d", &q);
init();
while(q--) {
scanf("%d", &cmd);
if(cmd == ) {
scanf("%d %d %d %d", &a.y, &a.x, &b.y, &b.x);
line(a, b);
}
else {
char s[];
memset(s, , sizeof(s));
scanf("%d %d", &a.y, &a.x);
scanf("%s", s);
dfs(a.x, a.y, s[]);
}
}
for(int i = n - ; i >= ; i--) {
for(int j = ; j < m; j++) {
printf("%c", G[i][j]);
}
printf("\n");
}
}
return ;
}
3
201512-4 送货
图论小题，求一条不用回到原点的欧拉路，trick在图不连通的情况，因此要提前做一步连通性的判断。还有就是记录点的度，假如是奇数度的点为0个或者2个的时候是存在这样一条路的，假如奇数度点为1或者大于2则不存在。dfs的时候打好标记就可以了。
#include <algorithm>
#include <iostream>
#include <iomanip>
#include <cstring>
#include <climits>
#include <complex>
#include <fstream>
#include <cassert>
#include <cstdio>
#include <bitset>
#include <vector>
#include <deque>
#include <queue>
#include <stack>
#include <ctime>
#include <set>
#include <map>
#include <cmath> using namespace std; const int maxn = ;
const int maxm = ;
vector<int>::iterator it;
vector<int> G[maxn];
bool vis[maxn][maxn];
int dig[maxn];
int n, m, top;
int st[maxm];
int pre[maxn]; int find(int x) {
return x == pre[x] ? x : pre[x] = find(pre[x]);
} void unite(int x, int y) {
x = find(x);
y = find(y);
if(x != y) {
pre[y] = x;
}
}
inline void init() {
for(int i = ; i < maxn; i++) {
pre[i] = i;
}
} void dfs(int u) {
for(int i = ; i < G[u].size(); i++) {
if(!vis[u][G[u][i]]) {
vis[u][G[u][i]] = vis[G[u][i]][u] = ;
dfs(G[u][i]);
st[top++] = G[u][i];
}
}
} int main() {
// freopen("in", "r", stdin);
int a, b;
while(~scanf("%d %d", &n, &m)) {
init();
memset(dig, , sizeof(dig));
memset(vis, , sizeof(vis));
for(int i = ; i < n + ; i++) G[i].clear();
for(int i = ; i < m; i++) {
scanf("%d %d", &a, &b);
G[a].push_back(b);
G[b].push_back(a);
unite(a, b);
dig[a]++; dig[b]++;
}
int odd = ;
bool exflag = ;
int father = find();
for(int i = ; i <= n; i++) {
if(father != find(i)) exflag = ;
sort(G[i].begin(), G[i].end());
if(dig[i] & ) odd++;
}
if(odd == || odd > || exflag) {
puts("-1");
continue;
}
top = ;
dfs();
printf("");
while(top--) printf(" %d", st[top]);
printf("\n");
}
return ;
}
4
201512-5 矩阵
题目好长QAQ，不想做QAQ
看了一眼题应该是矩阵快速幂，怎么看怎么是个烂题。。