NEERC2014题解

A

结论题，行着取

int n, m;
 
signed main(void) {
#ifdef ONLINE_JUDGE
    freopen("alter.in","r",stdin);
    freopen("alter.out","w",stdout);
#endif
	read(n), read(m);
	writeln(n / 2 + m / 2);
	for (int i = 2; i <= n; i += 2)
		writeln(i, ' '), writeln(1, ' '), writeln(i, ' '), writeln(m);
	for (int i = 2; i <= m; i += 2)
		writeln(1, ' '), writeln(i, ' '), writeln(n, ' '), writeln(i);
	//fwrite(pf, 1, o1 - pf, stdout);
	return 0;
}

B

按照比值排序贪心取满。
liubw的代码：

const int N=1e5+10;
const db eps=1e-8;
int n,A,B;
struct node{
    int a,b,g,ip;
    bool operator < (const node o) const{
        return a*o.b>o.a*b;
    }
}p[N];
db ans[N];
 
void fst_IO(){
    freopen("burrito.in","r",stdin);
    freopen("burrito.out","w",stdout);
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cout<<fixed<<setprecision(12);
}
 
int main(){
    fst_IO();
    cin>>n>>A>>B;
    for(int i=1;i<=n;i++) cin>>p[i].g>>p[i].a>>p[i].b,p[i].ip=i;
    sort(p+1,p+1+n);
    
    db reca=0,recb=0;
    for(int i=1;i<=n;i++){
        db nd;
        if(p[i].b>0) nd=min(p[i].g,((db)B-recb)/p[i].b);
        else nd=p[i].g;
        reca+=nd*p[i].a,recb+=min((db)p[i].g*p[i].b,((db)B-recb));
        ans[p[i].ip]=nd;
    }
    if(reca<A) cout<<-1<<' '<<-1<<'\n';
    else{
        cout<<reca<<' '<<recb<<'\n';
        for(int i=1;i<=n;i++) cout<<ans[i]<<" \n"[n==i];
    }
    return 0;
}

E

有限状态自动机是唬人的本质上是只要找到图上的必胜环即可，dfs

int n, res[101], nxt[101][3];
int tot, ans[50001], p[50001][3];
inline void dfs(int &x, vector<int> state, int len) {
	x = ++tot;
	p[x][0] = p[x][1] = p[x][2] = 1;
	int cnt[3] = {0, 0, 0};
	for (int i : state) ++cnt[res[i]];
	if (cnt[0] * cnt[1] == 0 && cnt[0] * cnt[2] == 0 && cnt[1] * cnt[2] == 0) {
		ans[x] = (res[state[0]] + 1) % 3;
		int trans = res[state[0]];
		if (len < 2 * n) {
			for (int i = 0; i < state.size(); i++)
				state[i] = nxt[state[i]][ans[x]];
			dfs(p[x][trans], state, len + 1);
			return;
		}
		int u = state[0];
		int T = 0;
		do {
			if (res[u] == 0) u = nxt[u][1];
			else if (res[u] == 1) u = nxt[u][2];
			else u = nxt[u][0];
			++T;
		} while (u != state[0]);
		p[x][trans] = tot - T + 1;
		return;
	}
	vector<int> s[3];
	for (int i : state) s[res[i]].push_back(nxt[i][0]);
	for (int i = 0; i < 3; i++) {
		sort(s[i].begin(), s[i].end());
		int l = unique(s[i].begin(), s[i].end()) - s[i].begin();
		while (s[i].size() > l) s[i].pop_back();
	}
	ans[x] = 0;
	for (int i = 0; i < 3; i++)
		if (cnt[i]) dfs(p[x][i], s[i], 0);
}
 
signed main(void) {
	freopen("epic.in", "r", stdin);
	freopen("epic.out", "w", stdout);
	cin >> n;
	for (int i = 1; i <= n; i++) {
		char c;
		cin >> c;
		if (c == 'R') res[i] = 0;
		if (c == 'P') res[i] = 1;
		if (c == 'S') res[i] = 2;
		cin >> nxt[i][0] >> nxt[i][1] >> nxt[i][2];
	}
	vector<int> state;
	for (int i = 1; i <= n; i++) state.push_back(i);
	int rt;
	dfs(rt, state, 0);
	cout << tot << endl;
	for (int i = 1; i <= tot; i++) {
		if (ans[i] == 0) putchar('R');
		if (ans[i] == 1) putchar('P');
		if (ans[i] == 2) putchar('S');
		for (int j = 0; j < 3; j++) cout << ' ' << p[i][j];
		cout << endl;
	}
	//fwrite(pf, 1, o1 - pf, stdout);
	return 0;
}

I

本质是求多少个线段能互相包含，就是LIS问题的变种。用树状数组优化DP即可。

const int N = 2e5 + 5;
int n, p[N], f[N], g[N];
 
struct BIT {
	int c[N];
	inline void update(int x, int v) {
		for (; x <= n; x += lowbit(x)) chkmax(c[x], v);
	}
	
	inline int query(int x) {
		int ret = 0;
		for (; x; x -= lowbit(x)) chkmax(ret, c[x]);
		return ret;
	}
} F, G;
 
signed main(void) {
#ifdef ONLINE_JUDGE
	freopen("improvements.in","r",stdin);
	freopen("improvements.out","w",stdout);
#endif
	read(n); int ans = 0;
	for (int i = 1; i <= n; i++) read(p[i]);
	for (int i = 1; i <= n; i++) {
		f[i] = F.query(p[i]) + 1;
		g[i] = G.query(n - p[i] + 1) + 1;
		chkmax(ans, f[i] + g[i] - 1);
		F.update(p[i], f[i]);
		G.update(n - p[i] + 1, g[i]);
	}
	
	writeln(ans);
	//fwrite(pf, 1, o1 - pf, stdout);
	return 0;
}

J

先算出n，然后dfs就可以了。

const int N = 2505;
char s[N]; int n, m, h[N]; vector <int> ans;
 
inline void dfs(int d, int lst) {
	if (d > m && lst == -1 && ans.size() == n) {
		for (auto u : ans) writeln(u, ' ');
		exit(0);
	}
	if (lst == -1) {
		if (!h[s[d] - '0']) h[s[d] - '0'] = 1, ans.push_back(s[d] - '0'), dfs(d + 1, -1), h[s[d] - '0'] = 0, ans.pop_back();
		if (d < m) dfs(d + 1, s[d] - '0');
	} else {
		int val = 10 * lst + s[d] - '0';
		if (val <= n && !h[val]) h[val] = 1, ans.push_back(val), dfs(d + 1, -1), h[val] = 0, ans.pop_back();
	}
}
 
signed main(void) {
#ifdef ONLINE_JUDGE
	freopen("joke.in","r",stdin);
	freopen("joke.out","w",stdout);
#endif
	readstr(s + 1); m = strlen(s + 1);
	int s = 0;
	for (n = 1; n <= 50; n++) {
		if (n < 10) s++;
		else s += 2;
		if (s == m) break;
	}
	dfs(1, -1);
	//fwrite(pf, 1, o1 - pf, stdout);
	return 0;
}