模拟赛小结：2017 China Collegiate Programming Contest Final (CCPC-Final 2017)-球迷互动区-世界杯预选赛积分榜|阿根廷世界杯|好好好123世界杯乐活站|haohaohao123.com

模拟赛小结：2017 China Collegiate Programming Contest Final (CCPC-Final 2017)

比赛链接：传送门

前期大顺风，2：30金区中游。后期开题乏力，掉到银尾。4：59绝杀I，但罚时太高卡在银首。

Problem A - Dogs and Cages 00：09：45 （+） Solved by Dancepted

算了半天发现就是n-1，被队友喷死，差点气哭。

Problem E - Evil Forest 00：16：54 （+） Solved by xk

xk大喊签到，就过了。

代码：

#include

#define fast ios::sync_with_stdio(false), cin.tie(0), cout.tie(0)

#define N 100005

#define M 100005

#define INF 0x3f3f3f3f

#define mk(x) (1<

#define sz(x) ((int)x.size())

#define upperdiv(a,b) (a/b + (a%b>0))

#define mp(a,b) make_pair(a, b)

#define endl '\n'

#define lowbit(x) (x&-x)

using namespace std;

typedef long long ll;

typedef double db;

/** fast read **/

template

inline void read(T &x) {

x = 0; T fg = 1; char ch = getchar();

while (!isdigit(ch)) {

if (ch == '-') fg = -1;

ch = getchar();

}

while (isdigit(ch)) x = x*10+ch-'0', ch = getchar();

x = fg * x;

}

template

inline void read(T &x, Args &... args) { read(x), read(args...); }

template

inline void write(T x) {

int len = 0; char c[21]; if (x < 0) putchar('-'), x = -x;

do{++len; c[len] = x%10 + '0';} while (x /= 10);

for (int i = len; i >= 1; i--) putchar(c[i]);

}

template

inline void write(T x, Args ... args) { write(x), write(args...); }

int main() {

fast;

int T, kase = 1;

cin >> T;

while (T--) {

int n;

cin >> n;

int ans = 0;

for(int i = 0; i < n; i++)

{

int x;

cin >> x;

ans += x + upperdiv(x, 10);

}

cout << "Case #" << (kase++) << ": " << ans << endl;

}

return 0;

}

View Code

Problem C - Rich Game 00：32：42 （+） Solved by xk

xk又喊了一声签到！

代码：

#include

#define fast ios::sync_with_stdio(false), cin.tie(0), cout.tie(0)

#define N 100005

#define M 100005

#define INF 0x3f3f3f3f

#define mk(x) (1<

#define sz(x) ((int)x.size())

#define upperdiv(a,b) (a/b + (a%b>0))

#define mp(a,b) make_pair(a, b)

#define endl '\n'

#define lowbit(x) (x&-x)

using namespace std;

typedef long long ll;

typedef double db;

/** fast read **/

template

inline void read(T &x) {

x = 0; T fg = 1; char ch = getchar();

while (!isdigit(ch)) {

if (ch == '-') fg = -1;

ch = getchar();

}

while (isdigit(ch)) x = x*10+ch-'0', ch = getchar();

x = fg * x;

}

template

inline void read(T &x, Args &... args) { read(x), read(args...); }

template

inline void write(T x) {

int len = 0; char c[21]; if (x < 0) putchar('-'), x = -x;

do{++len; c[len] = x%10 + '0';} while (x /= 10);

for (int i = len; i >= 1; i--) putchar(c[i]);

}

template

inline void write(T x, Args ... args) { write(x), write(args...); }

int main() {

fast;

int T, kase = 1;

cin >> T;

while (T--) {

int x, y, k;

cin >> x >> y >> k;

int money = 0, ans = 0;

if(x > y) ans = k;

else

{

for(int i = 0; i < k; i++)

{

if(money + 9 * x >= 11 * y) {

money += 9 * x - 11 * y;

ans++;

}

else {

money += 11 * x;

}

cout << "Case #" << (kase++) << ": " << ans << endl;

}

return 0;

}

View Code

Problem K - Knightmare 00：46：33 （+） Solved by Dancepted

步数较少的时候可以往回走，把没走过的地方填上，步数增长到一定程度时，答案差不多会均匀增长。

我猜测是小数据打表，大数据是个公式之类的。

开完A趁电脑没人就打了个表，发现和我的猜测是一致的，果断交了一发就过了。

代码：

#include

#define fast ios::sync_with_stdio(false), cin.tie(0), cout.tie(0)

#define N 1005

#define M 100005

#define INF 0x3f3f3f3f

#define mk(x) (1<

#define sz(x) ((int)x.size())

#define upperdiv(a,b) (a/b + (a%b>0))

#define mp(a,b) make_pair(a, b)

#define endl '\n'

#define lowbit(x) (x&-x)

using namespace std;

typedef __int128 ll;

typedef double db;

/** fast read **/

template

inline void read(T &x) {

x = 0; T fg = 1; char ch = getchar();

while (!isdigit(ch)) {

if (ch == '-') fg = -1;

ch = getchar();

}

while (isdigit(ch)) x = x*10+ch-'0', ch = getchar();

x = fg * x;

}

template

inline void read(T &x, Args &... args) { read(x), read(args...); }

template

inline void write(T x) {

int len = 0; char c[21]; if (x < 0) putchar('-'), x = -x;

do{++len; c[len] = x%10 + '0';} while (x /= 10);

for (int i = len; i >= 1; i--) putchar(c[i]);

}

template

inline void write(T x, Args ... args) { write(x), write(args...); }

const int ans[10] = {1, 9, 41, 109, 205, 325};

int main() {

int T; cin >> T;

int kase = 1;

while (T--) {

ll n; read(n);

printf("Case #%d: ", kase++);

if (n <= 5) {

write(ans[n]);

}

else {

ll res = 14 * n * n - 6 * n + 5;

write(res);

}

putchar('\n');

}

return 0;

}

View Code

Problem J - Subway Chasing 01：42：00 （+） Solved by xk & lh

好像是差分约束什么的。图论这种事相信队友就完了。

代码：

#include

#define fast ios::sync_with_stdio(false), cin.tie(0), cout.tie(0)

#define N 100005

#define M 100005

#define INF 0x3f3f3f3f

#define mk(x) (1<

#define sz(x) ((int)x.size())

#define upperdiv(a,b) (a/b + (a%b>0))

#define mp(a,b) make_pair(a, b)

#define endl '\n'

#define lowbit(x) (x&-x)

using namespace std;

typedef long long ll;

typedef double db;

/** fast read **/

template

inline void read(T &x) {

x = 0; T fg = 1; char ch = getchar();

while (!isdigit(ch)) {

if (ch == '-') fg = -1;

ch = getchar();

}

while (isdigit(ch)) x = x*10+ch-'0', ch = getchar();

x = fg * x;

}

template

inline void read(T &x, Args &... args) { read(x), read(args...); }

template

inline void write(T x) {

int len = 0; char c[21]; if (x < 0) putchar('-'), x = -x;

do{++len; c[len] = x%10 + '0';} while (x /= 10);

for (int i = len; i >= 1; i--) putchar(c[i]);

}

template

inline void write(T x, Args ... args) { write(x), write(args...); }

const int maxn = 2000 + 5;

struct edge

{

int v, l;

};

ll dis[maxn];

int cnt[maxn];

bool inq[maxn];

vector g[maxn];

void addedge(int u, int v, int l)

{

g[u].push_back(edge{v, l});

// g[v].push_back(edge{u, l});

}

int n, m, x;

bool spfa()

{

queue q;

dis[1] = 0;

q.push(1);

cnt[1] = inq[1] = 1;

while(!q.empty())

{

int u = q.front();

inq[u] = 0;

q.pop();

for(auto &e : g[u])

{

if(dis[e.v] > dis[u] + e.l)

{

dis[e.v] = dis[u] + e.l;

if(!inq[e.v]) {

cnt[e.v]++;

if(cnt[e.v] >= n) return false;

q.push(e.v);

inq[e.v] = 1;

}

return true;

}

int main()

{

fast;

int T, kase = 1;

cin >> T;

while (T--)

{

cin >> n >> m >> x;

for(int i = 1; i <= n; i++)

{

g[i].clear();

dis[i] = 1e18;

cnt[i] = inq[i] = 0;

}

for(int i = 1; i < n; i++)

{

addedge(i+1, i, -1);

addedge(i, i+1, 2e9);

}

for(int i = 0; i < m; i++)

{

int a, b, c, d;

cin >> a >> b >> c >> d;

if(a == b)

{

if(c == d)

{

addedge(a, c, x);

addedge(c, a, -x);

}

else

{

addedge(a, c, x - 1);

addedge(d, a, -x - 1);

}

else

{

if(c == d)

{

addedge(b, c, x - 1);

addedge(c, a, -x - 1);

}

else

{

addedge(b, c, x - 1);

addedge(d, a, -x - 1);

}

cout << "Case #" << (kase++);

if(!spfa()) cout << " IMPOSSIBLE\n";

else {

for(int i = 2; i <= n; i++)

cout << ' ' << dis[i] - dis[i - 1];

cout << endl;

}

return 0;

}

View Code

Problem G - Alice’s Stamps 02：24：14 （-2） Solved by Dancepted （dp）

上机的时候思路有乱，调出来之后交上去因为N开大了MLE返回CE，贡献了两发罚时。

dfs枚举当前搜索过的最右端点和剩下的k的数量，记忆化一下，状态数最多就$O(n^{2})$。

HDU的T组数据比较玄学，差点没敢交。

代码：$O(n^{2})$

#include

#define fast ios::sync_with_stdio(false), cin.tie(0), cout.tie(0)

#define N 2005

#define M 100005

#define INF 0x3f3f3f3f

#define mk(x) (1<

#define sz(x) ((int)x.size())

#define upperdiv(a,b) (a/b + (a%b>0))

#define mp(a,b) make_pair(a, b)

#define endl '\n'

#define lowbit(x) (x&-x)

using namespace std;

typedef long long ll;

typedef double db;

/** fast read **/

template

inline void read(T &x) {

x = 0; T fg = 1; char ch = getchar();

while (!isdigit(ch)) {

if (ch == '-') fg = -1;

ch = getchar();

}

while (isdigit(ch)) x = x*10+ch-'0', ch = getchar();

x = fg * x;

}

template

inline void read(T &x, Args &... args) { read(x), read(args...); }

template

inline void write(T x) {

int len = 0; char c[21]; if (x < 0) putchar('-'), x = -x;

do{++len; c[len] = x%10 + '0';} while (x /= 10);

for (int i = len; i >= 1; i--) putchar(c[i]);

}

template

inline void write(T x, Args ... args) { write(x), write(args...); }

struct Node{

int l, r;

bool operator < (const Node& x) const {

if (r == x.r) {

return l < x.l;

}

return r < x.r;

}

};

int n, m, k;

vector ns, ns1;

int ans = 0;

int f[N][N];

int dfs(int id, int r, int cnt, int resk) {

if (f[r][resk]) {

return f[r][resk];

}

if (resk == 0) {

return 0;

}

if (id >= sz(ns)) {

return 0;

}

int tmp = dfs(id+1, r, cnt, resk);

tmp = max(tmp, ns[id].r - max(ns[id].l-1, r) + dfs(id+1, ns[id].r, cnt + ns[id].r - max(ns[id].l-1, r), resk-1));

ans = max(ans, cnt + tmp);

return f[r][resk] = tmp;

}

bool ok[N];

int l[N], r[N];

int main() {

int T, kase = 1;

cin >> T;

while (T--) {

ns.clear(), ns1.clear();

read(n, m, k);

for (int i = 1; i <= m; i++) {

read(l[i], r[i]);

ok[i] = true;

}

for (int i = 1; i <= m; i++) {

for (int j = 1; j <= m; j++) if (i != j) {

if (l[i] < l[j] && r[j] <= r[i]) {

ok[j] = false;

}

for (int i = 1; i <= m; i++) if (ok[i]) {

ns.push_back(Node{l[i], r[i]});

}

sort(ns.begin(), ns.end());

// init();

ans = 0;

for (int i = 0; i <= n; i++) {

for (int j = 0; j <= k; j++) {

f[i][j] = 0;

}

dfs(0, 0, 0, k);

printf("Case #%d: %d\n", kase++, ans);

}

return 0;

}

View Code

题解的做法是一个很好写的dp：

$f_{i, j}$表示最右边的覆盖点是i的情况下，用了j个集合的最大覆盖长度。

代码：$O(n^{2})$

#include

#define fast ios::sync_with_stdio(false), cin.tie(0), cout.tie(0)

#define N 2005

#define M 100005

#define INF 0x3f3f3f3f

#define mk(x) (1<

#define sz(x) ((int)x.size())

#define upperdiv(a,b) (a/b + (a%b>0))

#define mp(a,b) make_pair(a, b)

#define endl '\n'

#define lowbit(x) (x&-x)

using namespace std;

typedef long long ll;

typedef double db;

/** fast read **/

template

inline void read(T &x) {

x = 0; T fg = 1; char ch = getchar();

while (!isdigit(ch)) {

if (ch == '-') fg = -1;

ch = getchar();

}

while (isdigit(ch)) x = x*10+ch-'0', ch = getchar();

x = fg * x;

}

template

inline void read(T &x, Args &... args) { read(x), read(args...); }

template

inline void write(T x) {

int len = 0; char c[21]; if (x < 0) putchar('-'), x = -x;

do{++len; c[len] = x%10 + '0';} while (x /= 10);

for (int i = len; i >= 1; i--) putchar(c[i]);

}

template

inline void write(T x, Args ... args) { write(x), write(args...); }

int mxr[N];

int f[N][N];

int main() {

int T; cin >> T;

for (int kase = 1; kase <= T; kase++) {

int n, m, k; read(n, m, k);

memset(mxr, 0, (n+1) * sizeof(int));

for (int i = 0; i <= n; i++) {

for (int j = 0; j <= k; j++) {

f[i][j] = 0;

}

for (int i = 1; i <= m; i++) {

int l, r; read(l, r);

mxr[l] = max(mxr[l], r);

}

int ans = 0, r = 0;

for (int i = 1; i <= n; i++) {

r = max(mxr[i], r);

for (int j = 0; j <= k; j++) {

f[i][j] = max(f[i][j], f[i-1][j]);

ans = max(ans, f[i][j]);

if (j+1 <= k)

f[r][j+1] = max(f[r][j+1], f[i-1][j] + r - i + 1),

ans = max(ans, f[r][j+1]);

}

printf("Case #%d: %d\n", kase, ans);

}

return 0;

}

View Code

Problem I - Inkopolis 04：59：59 （-3） Solved by Dancepted & xk

中午还在看的基环树下午就用到了。

先考虑树上的情况。会影响答案的部分只有修改颜色之前的颜色$color_{pre}$，和之后的颜色$color_{now}$两种。看是否会新增、删除color region，或者合并、分割原来的color region。

再考虑环上的情况。同上。特别地：如果整个环都是同一种颜色，修改了颜色不会分割原来的color region；如果整个环除了修改的边都是$color_{now}$，则修改颜色不会合并color region。

计算节日开始前各街道的颜色，可以模仿修改的操作，一条条边加入就行了。

实现的时候先把环扣出来，统计一下环各颜色的边数量。用个map保存每个点相邻的各颜色的数量。再用map保存每条边的颜色。

然后扫一遍所有的边先计算初始情况下的region的数量sum，然后一次次修改边的颜色，更新sum就好了。

代码：O(nlogn)

#include

#define fast ios::sync_with_stdio(false), cin.tie(0), cout.tie(0)

#define N 200005

#define M 200005

#define INF 0x3f3f3f3f

#define mk(x) (1<

#define sz(x) ((int)x.size())

#define upperdiv(a,b) (a/b + (a%b>0))

#define mp(a,b) make_pair(a, b)

#define endl '\n'

#define lowbit(x) (x&-x)

using namespace std;

typedef long long ll;

typedef double db;

/** fast read **/

template

inline void read(T &x) {

x = 0; T fg = 1; char ch = getchar();

while (!isdigit(ch)) {

if (ch == '-') fg = -1;

ch = getchar();

}

while (isdigit(ch)) x = x*10+ch-'0', ch = getchar();

x = fg * x;

}

template

inline void read(T &x, Args &... args) { read(x), read(args...); }

template

inline void write(T x) {

int len = 0; char c[21]; if (x < 0) putchar('-'), x = -x;

do{++len; c[len] = x%10 + '0';} while (x /= 10);

for (int i = len; i >= 1; i--) putchar(c[i]);

}

template

inline void write(T x, Args ... args) { write(x), write(args...); }

int tot;

int head[N], nxt[N<<1], ver[N<<1], col[N<<1];

void addEdge(int u, int v, int c) {

nxt[tot] = head[u], ver[tot] = v, col[tot] = c, head[u] = tot++;

}

int iscir[N], cirlen;

bool vis[N];

int getCir(int u, int fa, int& rt) {

vis[u] = true;

for (int i = head[u]; i != -1; i = nxt[i]) {

int v = ver[i];

if (v == fa) continue;

if (vis[v]) {

rt = v;

iscir[u] = 1;

cirlen++;

return 1;

}

else {

int tmpcir = getCir(v, u, rt);

if (tmpcir) {

iscir[u] = tmpcir;

cirlen++;

return u != rt;

}

return 0;

}

int cnt[N];

int sum;

map mp[N];

map, int> uv_col;

void update(int u, int v, int ccur, bool ifprint) {

if (u > v) swap(u, v);

int cpre = uv_col[mp(u, v)];

if (cpre == ccur) {

if (ifprint)

printf("%d\n", sum);

return;

}

if (!iscir[u] || !iscir[v]) {

//on tree

if (mp[u][cpre] >= 2 && mp[v][cpre] >= 2) {

sum++;

}

if (mp[u][cpre] == 1 && mp[v][cpre] == 1) {

sum--;

}

if (mp[u][ccur] && mp[v][ccur]) {

sum--;

}

if (!mp[u][ccur] && !mp[v][ccur]) {

sum++;

}

else {

//on circle

if (mp[u][cpre] >= 2 && mp[v][cpre] >= 2) {

if (cnt[cpre] != cirlen)

sum++;

}

if (mp[u][cpre] == 1 && mp[v][cpre] == 1) {

sum--;

}

if (mp[u][ccur] && mp[v][ccur]) {

if (cnt[ccur] != cirlen-1)

sum--;

}

if (!mp[u][ccur] && !mp[v][ccur]) {

sum++;

}

if (cpre != -1)

cnt[cpre]--;

cnt[ccur]++;

}

uv_col[mp(u, v)] = ccur;

if (cpre != -1) {

mp[u][cpre]--;

mp[v][cpre]--;

}

mp[u][ccur]++;

mp[v][ccur]++;

if (ifprint)

printf("%d\n", sum);

}

int main() {

int T;

cin >> T;

for (int kase = 1; kase <= T; kase++) {

int n, m; read(n, m);

// init

uv_col.clear();

for (int i = 1; i <= n; i++) {

mp[i].clear();

}

tot = 0;

memset(head, -1, (n+1) * sizeof(int));

// input and count colors on every edge

for (int i = 1; i <= n; i++) {

int u, v, c; read(u, v, c);

addEdge(u, v, c);

addEdge(v, u, c);

if (u > v)

swap(u, v);

uv_col[mp(u, v)] = -1;

// mp[u][c]++; mp[v][c]++;

}

// get circle

int rt = -1;

memset(vis, false, (n+1) * sizeof(bool));

memset(iscir, 0, (n+1) * sizeof(int));

cirlen = 0;

getCir(1, -1, rt);

// count colors on circle

memset(cnt, 0, (n+1) * sizeof(int));

sum = 0;

for (int i = 0; i < n; i++) {

int u = ver[i<<1], v = ver[i<<1|1], ccur = col[i<<1];

update(u, v, ccur, false);

}

printf("Case #%d:\n", kase);

for (int i = 1; i <= m; i++) {

int u, v, ccur; read(u, v, ccur);

update(u, v, ccur, true);

}

return 0;

}

11111

5 10

1 5 1

2 5 1

3 5 1

4 5 1

1 2 1

4 4

1 2 1

2 3 1

3 4 1

4 1 1

1 2 2

3 4 2

2 3 2

4 1 4

4 3

4 2 4

2 3 3

3 4 2

1 4 1

3 4 2

2 3 4

3 4 3

View Code

总结：

本场能绝杀还是有点运气成分在的，而且现场赛的话最后几分钟可能就交不上题了也可能。不过绝杀也不影响苟在银牌，问题不大。

然后最近的几场好像都是我在贡献罚时，感觉码力出现了一些小小的问题。这两天要小心一点。

然后还有两周可能就要退役了，模拟赛还没有进过金区感觉很难受啊，打成这个样子还怎么冲金啊qaq。

世界杯预选赛积分榜|阿根廷 世界杯|好好好123世界杯乐活站|haohaohao123.com

模拟赛小结：2017 China Collegiate Programming Contest Final (CCPC-Final 2017)

世界杯预选赛积分榜|阿根廷世界杯|好好好123世界杯乐活站|haohaohao123.com