开黑被Skip...白打了一场= =，rating没升也没降。。。（论开黑的正确姿势）
A题：
题目描述：
求一个人在一个节点数为n的环上，从a位置走b步会到哪个位置。
题解：
水题，直接模就好了。
代码：
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#ifdef WIN32
#define LL "%I64d"
#else
#define LL "%lld"
#endif
#ifdef CT
#define debug(...) printf(__VA_ARGS__)
#define setfile()
#else
#define debug(...)
#define filename ""
#define setfile() freopen(filename".in", "r", stdin); freopen(filename".out", "w", stdout);
#endif
#define R register
#define getc() (S == T && (T = (S = B) + fread(B, 1, 1 << 15, stdin), S == T) ? EOF : *S++)
#define dmax(_a, _b) ((_a) > (_b) ? (_a) : (_b))
#define dmin(_a, _b) ((_a) < (_b) ? (_a) : (_b))
#define cmax(_a, _b) (_a < (_b) ? _a = (_b) : 0)
#define cmin(_a, _b) (_a > (_b) ? _a = (_b) : 0)
#define For(_i, _a, _b) for (R int (_i) = (_a); (_i) <= (_b); ++(_i))
#define Rep(_i, _a, _b) for (R int (_i) = (_b); (_i) >= (_a); ++(_i))
char B[1 << 15], *S = B, *T = B;
inline int FastIn()
{
R char ch; R int cnt = 0; R bool minus = 0;
while (ch = getc(), (ch < '0' || ch > '9') && ch != '-') ;
ch == '-' ? minus = 1 : cnt = ch - '0';
while (ch = getc(), ch >= '0' && ch <= '9') cnt = cnt * 10 + ch - '0';
return minus ? -cnt : cnt;
}
int main()
{
// setfile();
R int n = FastIn(), a = FastIn(), b = FastIn();
R int ans = a + b;
while (ans < 0) ans += n;
while (ans > n) ans -= n;
printf("%d
",ans == 0 ? n : ans );
return 0;
}
B题：
题目描述：
给定n个人和m个队伍，每个人有一个名字，所属队伍和能力值。求每个队伍能力值前两名的名字。如果前两名不只两个人则输出“？”
题解：
按队伍为第一关键字，能力值为第二关键字排序。然后搞一搞就好了。当时考场上想复杂了，分类讨论了半天，推掉了重写了好几遍。悲催！
代码：
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#ifdef WIN32
#define LL "%I64d"
#else
#define LL "%lld"
#endif
#ifdef CT
#define debug(...) printf(__VA_ARGS__)
#define setfile()
#else
#define debug(...)
#define filename ""
#define setfile() freopen(filename".in", "r", stdin); freopen(filename".out", "w", stdout);
#endif
#define R register
#define getc() (S == T && (T = (S = B) + fread(B, 1, 1 << 15, stdin), S == T) ? EOF : *S++)
#define dmax(_a, _b) ((_a) > (_b) ? (_a) : (_b))
#define dmin(_a, _b) ((_a) < (_b) ? (_a) : (_b))
#define cmax(_a, _b) (_a < (_b) ? _a = (_b) : 0)
#define cmin(_a, _b) (_a > (_b) ? _a = (_b) : 0)
char B[1 << 15], *S = B, *T = B;
inline int FastIn()
{
R char ch; R int cnt = 0; R bool minus = 0;
while (ch = getc(), (ch < '0' || ch > '9') && ch != '-') ;
ch == '-' ? minus = 1 : cnt = ch - '0';
while (ch = getc(), ch >= '0' && ch <= '9') cnt = cnt * 10 + ch - '0';
return minus ? -cnt : cnt;
}
#define maxn 100010
struct people
{
char name[50];
int pos, v;
inline bool operator < (const people &that)const{return pos < that.pos || (pos == that.pos && v > that.v);}
}p[maxn], f[maxn], s[maxn];
bool err[maxn];
int main()
{
// setfile();
R int n, m;
scanf("%d %d
", &n, &m);
for (R int i = 1; i <= n; ++i)
{
scanf("%s %d %d
", p[i].name, &p[i].pos, &p[i].v);
}
std::sort(p + 1, p + n + 1);
for (R int i = 1; i <= n; ++i)
{
if (err[p[i].pos]) continue;
err[p[i].pos] = 1;
if (p[i].pos == p[i + 2].pos && (p[i].v == p[i + 2].v || p[i + 1].v == p[i + 2].v))
puts("?");
else
{
printf("%s %s
",p[i].name, p[i + 1].name );
}
}
return 0;
}
C题：
题目描述：
假装你已经有了n个玩具和m块钱。每一个玩具代表了一个数字，求你用m块钱最多能买多少你没有的玩具，输出方案。
题解：
贪心。从最小的开始买。买到不能买为止。
代码：
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#ifdef WIN32
#define LL "%I64d"
#else
#define LL "%lld"
#endif
#ifdef CT
#define debug(...) printf(__VA_ARGS__)
#define setfile()
#else
#define debug(...)
#define filename ""
#define setfile() freopen(filename".in", "r", stdin); freopen(filename".out", "w", stdout);
#endif
#define R register
#define getc() (S == T && (T = (S = B) + fread(B, 1, 1 << 15, stdin), S == T) ? EOF : *S++)
#define dmax(_a, _b) ((_a) > (_b) ? (_a) : (_b))
#define dmin(_a, _b) ((_a) < (_b) ? (_a) : (_b))
#define cmax(_a, _b) (_a < (_b) ? _a = (_b) : 0)
#define cmin(_a, _b) (_a > (_b) ? _a = (_b) : 0)
#define For(_i, _a, _b) for (R int (_i) = (_a); (_i) <= (_b); ++(_i))
#define Rep(_i, _a, _b) for (R int (_i) = (_b); (_i) >= (_a); ++(_i))
char B[1 << 15], *S = B, *T = B;
inline int FastIn()
{
R char ch; R int cnt = 0; R bool minus = 0;
while (ch = getc(), (ch < '0' || ch > '9') && ch != '-') ;
ch == '-' ? minus = 1 : cnt = ch - '0';
while (ch = getc(), ch >= '0' && ch <= '9') cnt = cnt * 10 + ch - '0';
return minus ? -cnt : cnt;
}
#define maxn 100010
int a[maxn], ans[maxn];
int main()
{
// setfile();
R int n = FastIn(), m = FastIn(), maxx = 0, pos = 1, tot = 0;
for (R int i = 1; i <= n; ++i)
a[i] = FastIn(), cmax(maxx, a[i]);
std::sort(a + 1, a + n + 1);
for (R int i = 1; m > 0; ++i)
{
// printf("%d %d
",i, m );
if (pos <= n && a[pos] == i) {pos ++;continue;}
m -= i;
ans[++tot] = i;
}
printf("%d
",m == 0? tot : tot -1 );
for (R int i = 1; i <= tot-1 ; ++i)
printf("%d ",ans[i] );
m == 0 ?printf("%d",ans[tot] ) : 0;
return 0;
}
D题：
题目描述：
在二维平面上给你n+1个点，然后这些点形成了一个回路，保证每条边与坐标轴平行。求有多少个线段所在直线穿过原封闭图形。
题解：
考场上又是写凸包又是写复杂的分类讨论的，结果比赛结束了才知道是找规律，并且结论是可以证明的。。。
代码：
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#ifdef WIN32
#define LL "%I64d"
#else
#define LL "%lld"
#endif
#ifdef CT
#define debug(...) printf(__VA_ARGS__)
#else
#define debug(...)
#endif
#define R register
#define getc() (S==T&&(T=(S=B)+fread(B,1,1<<15,stdin),S==T)?EOF:*S++)
#define gmax(_a, _b) ((_a) > (_b) ? (_a) : (_b))
#define gmin(_a, _b) ((_a) < (_b) ? (_a) : (_b))
#define cmax(_a, _b) (_a < (_b) ? _a = (_b) : 0)
#define cmin(_a, _b) (_a > (_b) ? _a = (_b) : 0)
char B[1<<15],*S=B,*T=B;
inline int FastIn()
{
R char ch;R int cnt=0;R bool minus=0;
while (ch=getc(),(ch < '0' || ch > '9') && ch != '-') ;
ch == '-' ?minus=1:cnt=ch-'0';
while (ch=getc(),ch >= '0' && ch <= '9') cnt = cnt * 10 + ch - '0';
return minus?-cnt:cnt;
}
int n;
int main()
{
n=FastIn();
printf("%d
",(n >> 1) - 2 );
return 0;
}
E题：
题目描述：
给定n个点和m条无向边，求不包含链的联通块的个数。
题解：
dfs。没啦！
代码：
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#ifdef WIN32
#define LL "%I64d"
#else
#define LL "%lld"
#endif
#ifdef CT
#define debug(...) printf(__VA_ARGS__)
#define setfile()
#else
#define debug(...)
#define filename ""
#define setfile() freopen(filename".in", "r", stdin); freopen(filename".out", "w", stdout);
#endif
#define R register
#define getc() (S == T && (T = (S = B) + fread(B, 1, 1 << 15, stdin), S == T) ? EOF : *S++)
#define dmax(_a, _b) ((_a) > (_b) ? (_a) : (_b))
#define dmin(_a, _b) ((_a) < (_b) ? (_a) : (_b))
#define cmax(_a, _b) (_a < (_b) ? _a = (_b) : 0)
#define cmin(_a, _b) (_a > (_b) ? _a = (_b) : 0)
char B[1 << 15], *S = B, *T = B;
inline int FastIn()
{
R char ch; R int cnt = 0; R bool minus = 0;
while (ch = getc(), (ch < '0' || ch > '9') && ch != '-') ;
ch == '-' ? minus = 1 : cnt = ch - '0';
while (ch = getc(), ch >= '0' && ch <= '9') cnt = cnt * 10 + ch - '0';
return minus ? -cnt : cnt;
}
#define maxn 100010
int last[maxn], ecnt, next[maxn << 1], to[maxn << 1], fa[maxn], ans;
bool vis[maxn], find;
#define add(_a, _b) (to[++ecnt] = (_b), next[ecnt] = last[_a], last[_a] = ecnt)
void dfs(R int x)
{
vis[x] = 1;
for (R int i = last[x]; i; i = next[i])
{
if (vis[to[i]] && fa[x] != to[i] && !find) {ans--;find = 1 ;break;}
else if (!vis[to[i]])
{
fa[to[i]] = x;
dfs(to[i]);
}
}
}
int main()
{
// setfile();
R int n = FastIn(), m = FastIn();
for (R int i = 1; i <= m; ++i)
{
R int a = FastIn(), b = FastIn();
add(a, b);add(b, a);
}
for (R int i = 1; i <= n; ++i)
if (!vis[i]) find = 0, dfs(i), ans++;
printf("%d
",ans);
return 0;
}
F题：
题目描述：
给你一个N*M的矩阵，以及一个数K，你可以把矩阵里的数减少，使得剩下一个权值全部为某个数的四联通块（其他数都为0），且矩阵内所有数的和必须为K，且这个联通块里必须有一个数没有修改，修改只支持减法。
题解：
这题的限制条件有点多。做法就是先把权值排序，然后一个一个判断，用并查集维护已经出现过的数的联通块，如果某个数能被K整除且所在的已经出现的联通块的大小大于K/V，则输出答案。
代码：
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <queue>
#ifdef WIN32
#define LL "%I64d"
#else
#define LL "%lld"
#endif
#ifdef CT
#define debug(...) printf(__VA_ARGS__)
#define setfile()
#else
#define debug(...)
#define filename ""
#define setfile() freopen(filename".in", "r", stdin); freopen(filename".out", "w", stdout);
#endif
#define R register
#define getc() (S == T && (T = (S = B) + fread(B, 1, 1 << 15, stdin), S == T) ? EOF : *S++)
#define dmax(_a, _b) ((_a) > (_b) ? (_a) : (_b))
#define dmin(_a, _b) ((_a) < (_b) ? (_a) : (_b))
#define cmax(_a, _b) (_a < (_b) ? _a = (_b) : 0)
#define cmin(_a, _b) (_a > (_b) ? _a = (_b) : 0)
char B[1 << 15], *S = B, *T = B;
inline int FastIn()
{
R char ch; R int cnt = 0; R bool minus = 0;
while (ch = getc(), (ch < '0' || ch > '9') && ch != '-') ;
ch == '-' ? minus = 1 : cnt = ch - '0';
while (ch = getc(), ch >= '0' && ch <= '9') cnt = cnt * 10 + ch - '0';
return minus ? -cnt : cnt;
}
inline long long FastIn2()
{
R char ch; R long long cnt = 0; R bool minus = 0;
while (ch = getc(), (ch < '0' || ch > '9') && ch != '-') ;
ch == '-' ? minus = 1 : cnt = ch - '0';
while (ch = getc(), ch >= '0' && ch <= '9') cnt = cnt * 10 + ch - '0';
return minus ? -cnt : cnt;
}
#define maxn 2000010
struct poi
{
int x, y, v;
inline bool operator < (const poi &that) const {return v > that.v;}
}buff[maxn];
bool vis[maxn];
int Fa[maxn], size[maxn], ans[1010][1010];
#define pos(_i , _j) (((_i) - 1) * m + (_j))
int Find(R int x) {return Fa[x] == x ? x : Fa[x] = Find(Fa[x]);}
const int dx[4] = {0, 0, 1, -1}, dy[4] = {1, -1, 0, 0};
std::queue<int> q;
int main()
{
// setfile();
R int n = FastIn(), m = FastIn();R long long k = FastIn2(), cnt = 0;
for (R int i = 1; i <= n; ++i)
for (R int j = 1; j <= m; ++j)
{
buff[++cnt] = (poi){i, j, FastIn()};
}
std::sort(buff + 1, buff + cnt + 1);
for (R int i = 1; i <= cnt; ++i)
{
Fa[i] = i;
size[i] = 1;
}
for (R int i = 1; i <= cnt; ++i)
{
R int xx = buff[i].x, yy = buff[i].y, vv = buff[i].v;
vis[pos(xx, yy)] = 1;
R int f, f0 = Find(pos(xx, yy));
for (R int j = 0; j < 4; ++j)
{
R int nx = xx + dx[j], ny = yy + dy[j];
if (nx > 0 && nx <= n && ny > 0 && ny <= m && vis[pos(xx + dx[j], yy + dy[j])])
{
f = Find(pos(nx, ny));
if (f != f0)
{
Fa[f] = f0;
size[f0] += size[f];
}
}
}
if (k % vv != 0) continue;
if (size[f0] < k / vv) continue;
puts("YES");
q.push(pos(xx, yy));
R int cnt = k / vv - 1, tmp = cnt;
ans[xx][yy] = vv;
vis[pos(xx, yy)] = 0;
while (!q.empty() && cnt > 0)
{
R int now = q.front(); q.pop();
R int nx, ny = now % m;
!ny ? ny = m : 0;
nx = (now - ny) / m + 1;
for (R int j = 0; j < 4 && cnt > 0; ++j)
{
R int nex = nx + dx[j], ney = ny + dy[j];
if (nex > 0 && nex <= n && ney > 0 && ney <= m && Find(pos(nex, ney)) == f0 && vis[pos(nex, ney)])
ans[nex][ney] = vv, q.push(pos(nex, ney)), cnt--, vis[pos(nex, ney)] = 0;
}
}
for (R int ii = 1; ii <= n; ++ii)
{
for (R int jj = 1; jj <= m; ++jj) printf("%d ",ans[ii][jj] );
puts("");
}
return 0;
}
puts("NO");
return 0;
}
/*
4 3 8
2 2 2
1 1 1
1 2 1
1 1 1
*/
G题：
题目描述：
你有n个高度为hi的方块，然后你可以从上面开始取走一个联通块，求取的方案数。
题解：
DP。
代码：
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#ifdef WIN32
#define LL "%I64d"
#else
#define LL "%lld"
#endif
#ifdef CT
#define debug(...) printf(__VA_ARGS__)
#define setfile()
#else
#define debug(...)
#define filename ""
#define setfile() freopen(filename".in", "r", stdin); freopen(filename".out", "w", stdout);
#endif
#define R register
#define getc() (S == T && (T = (S = B) + fread(B, 1, 1 << 15, stdin), S == T) ? EOF : *S++)
#define dmax(_a, _b) ((_a) > (_b) ? (_a) : (_b))
#define dmin(_a, _b) ((_a) < (_b) ? (_a) : (_b))
#define cmax(_a, _b) (_a < (_b) ? _a = (_b) : 0)
#define cmin(_a, _b) (_a > (_b) ? _a = (_b) : 0)
char B[1 << 15], *S = B, *T = B;
inline int FastIn()
{
R char ch; R int cnt = 0; R bool minus = 0;
while (ch = getc(), (ch < '0' || ch > '9') && ch != '-') ;
ch == '-' ? minus = 1 : cnt = ch - '0';
while (ch = getc(), ch >= '0' && ch <= '9') cnt = cnt * 10 + ch - '0';
return minus ? -cnt : cnt;
}
#define maxn 1000010
const int mod = 1e9 + 7;
int h[maxn], f[maxn];
int main()
{
// setfile();
R int n = FastIn();
R long long ans = 0;
for (R int i = 1; i <= n; ++i) h[i] = FastIn() - 1;
for (R int i = 1; i <= n; ++i)
{
ans += h[i];
R int a = dmin(h[i - 1], h[i]);
R int b = dmin(a, h[i + 1]);
R int c = dmin(h[i], h[i + 1]);
ans = (1ll * f[i - 1] * a + ans) % mod;
f[i] = (1ll * f[i - 1] * b + c) % mod;
}
printf("%lld
",ans );
return 0;
}