A Rebus
题目大意
给定一个仅含加减法的数学表达式，要求将表达式中的问号换成\(1-n\)的整数，使得表达式成立
做法
贪心一下，首先可以把所有的问号填上1，然后贪心地修改每一个数，使得答案和n尽量靠近，如果改完最后一个数还是不能使答案变成n就无解。
代码
#include <iostream>
#include <cstdio>
#include <cstring>
#include <string>
#include <vector>
#include <cmath>
#include <cstdlib>
using namespace std;
vector<string> vec;
const int maxn = 1001;
int sgn[maxn], num[maxn];
int cur = 0;
int n;
int main()
{
string buf;
while (cin >> buf)
vec.push_back(buf);
for (int i = 0; i < vec.size(); i++)
{
if (vec[i] == "?")
{
if (i == 0 || vec[i - 1] == "+") sgn[i] = 1;
else sgn[i] = -1;
}
}
n = atoi(vec[vec.size() - 1].c_str());
for (int i = 0; i < vec.size(); i++)
{
if (sgn[i] == 1) {
num[i] = 1;
cur++;
} else if (sgn[i] == -1) {
num[i] = 1;
cur--;
}
}
for (int i = 0; i < vec.size(); i++)
{
if (sgn[i] == -1) {
if (cur > n) {
cur++;
num[i] = min(n, cur - n);
cur -= num[i];
}
} else if (sgn[i] == 1) {
if (cur < n) {
cur--;
num[i] = min(n, n - cur);
cur += num[i];
}
}
}
if (cur != n) {
printf("Impossible\n");
} else {
printf("Possible\n");
for (int i = 0; i < vec.size(); i++) {
if (vec[i] == "?")
{
if (i != 0) {
printf(" %d", num[i]);
} else {
printf("%d", num[i]);
}
} else {
printf(" %s", vec[i].c_str());
}
}
printf("\n");
}
return 0;
}
B International Olympiad
题目大意
给定一个1989年之后的年份的缩写，缩写的规则是这个年份在1989年之后没有使用过的最短后缀，要求复原。
做法
知道，从1989年到1998年，用完了所有的一位缩写，从1999年到2098年用完了所有的两位缩写，接着从2099年到3098年用完了所有的三位缩写……以此类推，因此我们可以根据后缀的长度推出年份的范围，之后又能发现在9999年之后，后缀长度与年份长度之差不超过1，所以暴力一下就好。
代码
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
int n;
char buf[111];
char ans[111], tans[111];
int main()
{
scanf("%d", &n);
for (int i = 0; i < n; i++)
{
scanf("%s", buf);
int yr = strlen(buf), tl = 0;
for (int i = 4; i < yr; i++)
tans[tl++] = buf[i];
tans[tl] = 0;
long long beg = 0, end = 0, e10 = 1;
yr -= 4;
while (yr--)
{
beg += e10;
e10 *= 10;
end += e10;
}
beg--;
beg += 1989;end += 1989;
for (int i = 0; i < 1000; i++) {
sprintf(buf, "%d%s", i, tans);
long long ttans = 0;
sscanf(buf, "%lld", &ttans);
if (beg <= ttans && ttans < end) {
printf("%lld\n", ttans);
break;
}
}
}
return 0;
}
C Graph Coloring
题目大意
给定一个图，最开始每条边都被染成了两种颜色中的一种，每次可以选择一个点，改变与这个点相连的所有边的颜色。问最少花多少次操作可以使所有边的颜色相同。
做法
我们知道以下两点事实，即
-
染色结果与顺序无关
-
每个点至多被选择一次
及一条推论：每条边之多被染色两次。
首先枚举两种颜色，即我们染色后整个图会变成哪种颜色，接着，对于某条边，我们知道如果它的颜色与最终的颜色相同，那么他的两个顶点要么全部被选择，要么都没被选择，而如果不同，则它的两个顶点中有且仅有一个被选择。
因而我们发现这是一个0/1染色的问题，我们可以通过DFS解决。
代码
#include <iostream>
#include <cstdio>
#include <cstring>
#include <vector>
#include <utility>
using namespace std;
const int maxn = 100000 + 1;
typedef pair<int, bool> pib;
#define v first
#define c second
int n, m, c[maxn];
vector<int> s[2], ts[2];
vector<pib> e[maxn];
bool dfs(int tar, int u)
{
for (pib edg : e[u])
{
if (c[edg.v] == -1)
{
c[edg.v] = (c[u] ^ edg.c ^ tar);
ts[c[edg.v]].push_back(edg.v);
if (!dfs(tar, edg.v)) return false;
} else {
if (c[edg.v] != (c[u] ^ edg.c ^ tar))
return false;
}
}
return true;
}
int main()
{
cin >> n >> m;
for (int i = 0; i < m; i++)
{
int u, v;
char cc[3];
cin >> u >> v >> cc;
e[u].push_back(pib(v, cc[0] == 'B'));
e[v].push_back(pib(u, cc[0] == 'B'));
}
bool res[2] = {1, 1};
for (int t = 0; t < 2; t++)
{
memset(c, -1, sizeof(c));
for (int i = 1; i <= n; i++)
{
if (c[i] == -1)
{
c[i] = 0;
ts[0].push_back(i);
res[t] = (res[t] && dfs(t, i));
bool flg = (ts[0].size() > ts[1].size());
s[t].insert(s[t].end(), ts[flg].begin(), ts[flg].end());
ts[0].clear();
ts[1].clear();
}
}
}
// I guess:
// if res[0] = false then
// we must have res[1] = false
int flg = ((res[0] && res[1]) ? (s[0].size() > s[1].size()) : (res[0] ? 0 : (res[1] ? 1 : -1)));
if (~flg)
{
printf("%lu\n", s[flg].size());
for (int v : s[flg])
printf("%d ", v);
printf("\n");
} else {
printf("-1\n");
}
return 0;
}