ExfJoe's Blog

感觉这场我们队三个人状态都不太好。。。最后出8题不过用时及罚时各种血崩。自己勉强出了4.5题，不过AJ两道签到题用了太久的时间。ORZ卓神单挑9题实力碾压。

A签到题，按题意判断就好。由于题目比较奇怪自己看了比较久才看懂题意。

#include <bits/stdc++.h>

typedef long long ll;
typedef unsigned int u32;
typedef unsigned long long ull;
typedef long double LD;
typedef std::pair<int, int> PII;
typedef std::vector<int> VI;

#define ST first
#define ND second
#define pb push_back
#define mp std::make_pair
#define ALL(x) x.begin(), x.end()
#define REP(i, a, b) for (int i = (a); i < (b); ++i)
#define PER(i, a, b) for (int i = (a); i > (b); --i)
#define FOR(i, a, b) for (int i = (a); i <= (b); ++i)
#define ROF(i, a, b) for (int i = (a); i >= (b); --i)
	
inline int read()
{
	static char ch;
	bool sgn = false;
	while (ch = getchar(), ch < '0' || ch > '9') if (ch == '-') sgn = true;
	int res = ch - 48;
	while (ch = getchar(), ch >= '0' && ch <= '9') res = res * 10 + ch - 48;
	return sgn ? -res : res;
}

const int N = 2e4 + 5;
int n, ansN;
std::string B = "@bmail.com", s, t[N], temp;
VI ans[N];
std::map<std::string, int> M;
	
int main()
{
	n = read();
	FOR(i, 1, n)
	{
		std::cin >> t[i];
		s = t[i];
		
		int l = s.size(), AT = 0;
		while (s[AT] != '@') ++AT;
		
		REP(j, 0, l) if (s[j] >= 'A' && s[j] <= 'Z')
			s[j] = (s[j] - 'A') + 'a';
		
		temp.clear();
		REP(j, AT, l) temp += s[j];
		
		if (temp == B)
		{
			std::string cur;
			cur.clear();
			REP(j, 0, AT)
			{
				if (s[j] == '+')
					break;
				if (s[j] != '.')
					cur += s[j];
			}
			s = cur + temp;
		}
		
		if (!M[s]) M[s] = ++ansN;
		ans[M[s]].pb(i);
		
		//std::cout << s << std::endl;
	}
	
	printf("%d\n", ansN);
	FOR(i, 1, ansN)
	{
		printf("%d ", (int)ans[i].size());
		REP(j, 0, (int)ans[i].size())
			std::cout << t[ans[i][j]] << " ";
		printf("\n");
	}
	return 0;
}

F，二分后贪心，当前时间选择能选择的食物中右端点最小的即可。队友这题打到一半没调出来去吃饭，我改了个细节A了。算作贡献+0.5吧

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <queue>
#define memcle(a) memset(a, 0, sizeof(a))
#define fo(i, a, b) for (i = a; i <= b; i++)
#define fd(i, a, b) for (i = a; i >= b; i--)
#define rep(i, n) for (i = 1; i <= n; i++)
using namespace std;
typedef long long LL;
typedef double LD;

const int N = 11000;
int n, maxt;

struct pro
{
    int s, t;
} a[N];

bool cmp(pro x, pro y) {return x.s < y.s;}

struct node
{
    int t, c;
    node(int _t = 0, int _c = 0) {t = _t, c = _c;}
};

bool operator<(const node &x, const node &y) {return (x.t == y.t) ? (x.c < y.c) : (x.t > y.t);}

priority_queue<node> heap;

bool work(int T)
{
    if (T == 0) return 1;
    for (; !heap.empty(); ) heap.pop();
    
    int j = 1;
    for (int i = 0; i <= maxt; i++)
    {
        for (; j <= n && a[j].s <= i; j++) heap.push(node(a[j].t, T));
        if (heap.empty()) continue;
        if (heap.top().t <= i) return false;
        int t = heap.top().t;
        int c = heap.top().c;
        heap.pop();
        if (c > 1) heap.push(node(t, c - 1));
    }
    if (!heap.empty()) return false;
    return true;
}

int main()
{
    
    scanf("%d", &n);
    for (int i = 1; i <= n; i++)
    {
        scanf("%d%d", &a[i].s, &a[i].t);
        maxt = max(maxt, a[i].t);
    }
    
    sort(a + 1, a + 1 + n, cmp);
    
    int l = 0, r = maxt;//ans = 0; // r = 10000
    while (l < r) 
    {
        int mid = (l + r + 1) / 2;
        if (work(mid)) l = mid; else r = mid - 1;
    }
    
    printf("%d\n", l * n);
    return 0;
}

G，将人按$d_i$排序，将天按$t_i$排序，按顺序处理每个人就可以使得对人有贡献的天的总变化次数为$O(n)$，用BIT统计，询问时二分答案即可。

#include <bits/stdc++.h>

typedef long long ll;
typedef unsigned int u32;
typedef unsigned long long ull;
typedef long double LD;
typedef std::pair<int, int> PII;
typedef std::vector<int> VI;

#define ST first
#define ND second
#define pb push_back
#define mp std::make_pair
#define ALL(x) x.begin(), x.end()
#define REP(i, a, b) for (int i = (a); i < (b); ++i)
#define PER(i, a, b) for (int i = (a); i > (b); --i)
#define FOR(i, a, b) for (int i = (a); i <= (b); ++i)
#define ROF(i, a, b) for (int i = (a); i >= (b); --i)
	
inline int read()
{
	static char ch;
	bool sgn = false;
	while (ch = getchar(), ch < '0' || ch > '9') if (ch == '-') sgn = true;
	int res = ch - 48;
	while (ch = getchar(), ch >= '0' && ch <= '9') res = res * 10 + ch - 48;
	return sgn ? -res : res;
}

const int N = 2e5 + 5;
int n, m, head, cur, now, temp, ans[N], t[N], d[N], r[N], p1[N], p2[N];
ll f1[N], f2[N];

inline bool cmp1(const int &x, const int &y)
{
	return t[x] < t[y];
}

inline bool cmp2(const int &x, const int &y)
{
	return d[x] < d[y];
}

inline void Add(ll *f, int x, const int &delta)
{
	for (; x <= m; x += x & -x)
		f[x] += delta;
}

inline ll Query(const ll *f, int x)
{
	ll res = 0;
	for (; x > 0; x -= x & -x)
		res += f[x];
	return res;
}

int main()
{
	n = read(); m = read();
	FOR(i, 1, m)
	{
		t[i] = read();
		p1[i] = i;
		Add(f1, i, 1);
		Add(f2, i, t[i]);
	}
	FOR(i, 1, n)
	{
		d[i] = read();
		r[i] = read();
		p2[i] = i;
	}
	
	std::sort(p1 + 1, p1 + m + 1, cmp1);
	std::sort(p2 + 1, p2 + n + 1, cmp2);
	
	head = 1; now = 1;
	FOR(i, 1, n)
	{
		cur = p2[i];
		
		while (head <= m && d[cur] >= t[p1[head]])
		{
			Add(f1, p1[head], -1);
			Add(f2, p1[head], -t[p1[head]]);
			++head;
		}
		
		ll sum = Query(f2, m) - (ll)Query(f1, m) * d[cur];
		if (sum < r[cur])
		{
			ans[cur] = 0;
			continue;
		}
		
		int L = 1, R = m, mid;
		while (L <= R)
		{
			mid = L + R >> 1;
			sum = Query(f2, mid) - (ll)Query(f1, mid) * d[cur];
			if (sum >= r[cur]) R = mid - 1;
			else L = mid + 1;
		}
		ans[cur] = L;
	}
	
	FOR(i, 1, n) printf("%d%c", ans[i], " \n"[i == n]);
	return 0;
}

H，结束前20min受卓神点拨，发现做出生成树后非树边对答案没有影响。。之前想了2h的非树边处理甚至还觉得可能是网络流。。感觉智商确实不足。

做出生成树后直接贪心匹配，子树内有未匹配的点则将它们先匹配起来，若最后还剩一个点，则根据当前点是否是关键点来确定这是当前子树的未匹配点还是与当前点匹配。

#include <bits/stdc++.h>

typedef long long ll;
typedef unsigned int u32;
typedef unsigned long long ull;
typedef long double LD;
typedef std::pair<int, int> PII;
typedef std::vector<int> VI;

#define ST first
#define ND second
#define pb push_back
#define mp std::make_pair
#define ALL(x) x.begin(), x.end()
#define REP(i, a, b) for (int i = (a); i < (b); ++i)
#define PER(i, a, b) for (int i = (a); i > (b); --i)
#define FOR(i, a, b) for (int i = (a); i <= (b); ++i)
#define ROF(i, a, b) for (int i = (a); i >= (b); --i)
	
inline int read()
{
	static char ch;
	bool sgn = false;
	while (ch = getchar(), ch < '0' || ch > '9') if (ch == '-') sgn = true;
	int res = ch - 48;
	while (ch = getchar(), ch >= '0' && ch <= '9') res = res * 10 + ch - 48;
	return sgn ? -res : res;
}

const int N = 5e4 + 5;
int n, m, K, num, a[N], b[N], fa[N];
int ecnt, adj[N], nxt[N * 2], go[N * 2];
VI ans[N];
bool vis[N], ok[N];

inline void addEdge(const int &u, const int &v)
{
	nxt[++ecnt] = adj[u]; adj[u] = ecnt; go[ecnt] = v;
	nxt[++ecnt] = adj[v]; adj[v] = ecnt; go[ecnt] = u;
}

inline int Dfs(const int &u)
{
	int last = 0;
	vis[u] = true;
	for (int e = adj[u]; e; e = nxt[e])
	{
		int v = go[e];
		if (vis[v]) continue;
		
		fa[v] = u;
		int p = Dfs(v);
		if (last && p)
		{
			int c1 = 0, c2 = 0;
			while (last != u) a[++c1] = last, last = fa[last];
			while (p != u) b[++c2] = p, p = fa[p];
			
			++num;
			FOR(i, 1, c1) ans[num].pb(a[i]);
			ans[num].pb(u);
			ROF(i, c2, 1) ans[num].pb(b[i]);
			
			last = 0;
		}
		else if (!last && p) last = p;
	}
	if (last && ok[u])
	{
		++num;
		while (last != u) ans[num].pb(last), last = fa[last];
		ans[num].pb(u);
		return 0;
	}
	else return ok[u] ? u : last;
}

int main()
{
	n = read(); m = read(); K = read();
	FOR(i, 1, m) addEdge(read(), read());
	FOR(i, 1, K) ok[read()] = true;
	
	FOR(i, 1, n) if (!vis[i])
		Dfs(i);
	
	printf("%d\n", num);
	FOR(i, 1, num)
	{
		printf("%d ", ans[i].size() - 1);
		REP(j, 0, ans[i].size())
			printf("%d ", ans[i][j]);
		printf("\n");
	}
	return 0;
}

J签到题，按题意模拟，记录下状态，碰到处理过的就说明出现循环，直接结束就好。

#include <bits/stdc++.h>

typedef long long ll;
typedef unsigned int u32;
typedef unsigned long long ull;
typedef long double LD;
typedef std::pair<int, int> PII;
typedef std::vector<int> VI;

#define ST first
#define ND second
#define pb push_back
#define mp std::make_pair
#define ALL(x) x.begin(), x.end()
#define REP(i, a, b) for (int i = (a); i < (b); ++i)
#define PER(i, a, b) for (int i = (a); i > (b); --i)
#define FOR(i, a, b) for (int i = (a); i <= (b); ++i)
#define ROF(i, a, b) for (int i = (a); i >= (b); --i)
	
inline int read()
{
	static char ch;
	bool sgn = false;
	while (ch = getchar(), ch < '0' || ch > '9') if (ch == '-') sgn = true;
	int res = ch - 48;
	while (ch = getchar(), ch >= '0' && ch <= '9') res = res * 10 + ch - 48;
	return sgn ? -res : res;
}

const int N = 20;
int n, m, sx, sy, sd, ans;
int dir[4][2] = {{-1, 0}, {0, 1}, {1, 0}, {0, -1}};	
char s[N];
bool go[N][N], used[N][N], sta[N][N][4];

inline bool cango(const int &x, const int &y)
{
	return x >= 1 && y >= 1 && x <= n && y <= m && !go[x][y];
}

int main()
{
	n = read(); m = read();
	FOR(i, 1, n)
	{
		scanf("%s", s + 1);
		FOR(j, 1, m)
		{
			if (s[j] == '.')
				used[i][j] = true;
			else if (s[j] == '*')
				go[i][j] = true;
			else
			{
				sx = i, sy = j;
				if (s[j] == 'U') sd = 0;
				if (s[j] == 'R') sd = 1;
				if (s[j] == 'D') sd = 2;
				if (s[j] == 'L') sd = 3;
			}
		}
	}
	
	while (!sta[sx][sy][sd])
	{
		sta[sx][sy][sd] = true;
		if (cango(sx + dir[sd][0], sy + dir[sd][1]))
		{
			sx += dir[sd][0];
			sy += dir[sd][1];
			if (used[sx][sy])
			{
				++ans;
				used[sx][sy] = false;
			}
		}
		else
		{
			sd = (sd + 1) % 4;
		}
	}
	printf("%d\n", ans + 1);
	return 0;
}