题解 [XJOI] CSP-S2开放一

期望得分 100+100+60 = 260
实际得分 30+20+70 = 120

T1

实际上是个暴力枚举
考场打炸了,RE30
订正代码

#include <cstdio>
#define ll long long
 
using namespace std;
 
const int p[] = {1, 10, 100, 1000, 10000, 100000, 1000000, 10000000, 100000000};
 
int main() {
    int t;
    scanf("%d", &t);
    while(t--) {
        ll cnt = 0;
        int l, r, tmp, n;
        scanf("%d %d", &l, &r);
        tmp = l; n = 0;
        while(tmp) {   
            tmp /= 10; ++n;
        }
        for(int i = l; i <= r; ++i) {
            tmp = i;
            int low = tmp % 10; tmp /= 10; tmp += low * p[n-1];
            while(tmp != i) {
                if(low && tmp >= l && tmp <= r) ++cnt;
                low = tmp % 10; tmp /= 10; tmp += low * p[n-1];
            }
        }
        printf("%lld\n", cnt / 2);
    }
    return 0;
}

T2

实际上就是最短路计数
考虑把下半边折上去,就满足对称性
然后跑最短路计数
这里建了虚拟节点0方便统计
考场上表头开小导致死循环了得分20,开大就对了
RE代码

#include <cstdio>
#include <cstring>
#include <queue>

using namespace std;

const int N = 123, MOD = 1000000009, INF = 0x3f3f3f3f;
int a[N][N];
int head[N], ver[N*N], wei[N*N], nex[N*N], tot;
inline void addedge(int u, int v, int w) {
	ver[tot] = v, wei[tot] = w, nex[tot] = head[u], head[u] = tot++;
}

struct node{
	int x, d;
	node() {}
	node(int X, int DIS) : x(X), d(DIS) {}
	bool operator < (const node& o) const { return d < o.d; }
};
priority_queue<node> q;
int dis[N*N], f[N*N];
void dij() {
	memset(dis, INF, sizeof(dis));
	memset(f, 0, sizeof(f));
	dis[1] = a[1][1]; f[1] = 1;
	q.push(node(1, dis[1]));
	while(!q.empty()) {
		node cur = q.top(); q.pop();
		if(-cur.d > dis[cur.x]) continue;
		for(int i = head[cur.x]; ~i; i = nex[i])
			if(dis[ver[i]] > dis[cur.x] + wei[i]) {
				dis[ver[i]] = dis[cur.x] + wei[i];
				f[ver[i]] = f[cur.x];
				q.push(node(ver[i], -dis[ver[i]]));
			} else if(dis[ver[i]] == dis[cur.x] + wei[i]) {
				f[ver[i]] = (f[cur.x] + f[ver[i]]) % MOD;
			}
				
	}
}

int main() {
	int n;
	while(~scanf("%d", &n) && n) {
		for(int i = 1; i <= n; ++i)
			for(int j = 1; j <= n; ++j) {
				scanf("%d", &a[i][j]);
				if(j > n+1-i) a[n+1-j][n+1-i] += a[i][j];
			}
		memset(head, -1, sizeof(head));
		tot = 0;
		for(int i = 1; i <= n; ++i)
			for(int j = 1; j <= n+1-i; ++j) {
					int cur = (i-1)*n+j;
					if(j != 1) addedge(cur, cur-1, a[i][j-1]);
					if(j != n+1-i) addedge(cur, cur+1, a[i][j+1]), addedge(cur, cur+n, a[i+1][j]);
					if(i != 1) addedge(cur, cur-n, a[i-1][j]);
					if(i+j == n+1) addedge((i-1)*n+j, 0, 0);
				}
		dij();
		printf("%d\n", f[0]);
	}
	return 0;
}

订正代码:

#include <cstdio>
#include <cstring>
#include <queue>

using namespace std;

const int N = 123, MOD = 1000000009, INF = 0x3f3f3f3f;
int a[N][N];
int head[N*N], ver[N*N*N], wei[N*N*N], nex[N*N*N], tot;
inline void addedge(int u, int v, int w) {
	ver[tot] = v, wei[tot] = w, nex[tot] = head[u], head[u] = tot++;
}

struct node{
	int x, d;
	node() {}
	node(int X, int DIS) : x(X), d(DIS) {}
	bool operator < (const node& o) const { return d < o.d; }
};
priority_queue<node> q;
int dis[N*N], f[N*N];
void dij() {
	memset(dis, INF, sizeof(dis));
	memset(f, 0, sizeof(f));
	dis[1] = a[1][1]; f[1] = 1;
	q.push(node(1, dis[1]));
	while(!q.empty()) {
		node cur = q.top(); q.pop();
		if(-cur.d > dis[cur.x]) continue;
		for(int i = head[cur.x]; ~i; i = nex[i])
			if(dis[ver[i]] > dis[cur.x] + wei[i]) {
				dis[ver[i]] = dis[cur.x] + wei[i];
				f[ver[i]] = f[cur.x];
				q.push(node(ver[i], -dis[ver[i]]));
			} else if(dis[ver[i]] == dis[cur.x] + wei[i]) {
				f[ver[i]] = (f[cur.x] + f[ver[i]]) % MOD;
			}
				
	}
}

int main() {
	int n;
	while(~scanf("%d", &n) && n) {
		for(int i = 1; i <= n; ++i)
			for(int j = 1; j <= n; ++j) {
				scanf("%d", &a[i][j]);
				if(j > n+1-i) a[n+1-j][n+1-i] += a[i][j];
			}
		memset(head, -1, sizeof(head));
		tot = 0;
		for(int i = 1; i <= n; ++i)
			for(int j = 1; j <= n+1-i; ++j) {
					int cur = (i-1)*n+j;
					if(j != 1) addedge(cur, cur-1, a[i][j-1]);
					if(j != n+1-i) addedge(cur, cur+1, a[i][j+1]), addedge(cur, cur+n, a[i+1][j]);
					if(i != 1) addedge(cur, cur-n, a[i-1][j]);
					if(i+j == n+1) addedge((i-1)*n+j, 0, 0);
				}
		dij();
		printf("%d\n", f[0]);
	}
	return 0;
}

T3

考场上打了个树上背包暴力
70

70分代码,树上背包

#include <cstdio>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 3456;
int head[N], ver[N<<1], nex[N<<1], tot, n;
inline void addedge(int u, int v) {
	ver[tot] = v; nex[tot] = head[u]; head[u] = tot++;
}
int a[N], f[N][N], lim;
void dfs(int cur, int pre) {
	for(int i = head[cur]; ~i; i = nex[i])
		if(pre != ver[i]) {
			dfs(ver[i], cur);
			for(int j = lim; ~j; --j)
				for(int k = j; ~k; --k)
					f[cur][j] = max(f[cur][j], f[cur][j-k] + f[ver[i]][k]);
		}
	for(int i = lim; i > 0; --i)
		f[cur][i] = f[cur][i-1] + a[cur];
}

int main() {
	memset(head, -1, sizeof(head));
	int u, v;
	scanf("%d %d", &n, &lim);
	for(int i = 1; i <= n; ++i) scanf("%d", a + i);
	for(int i = 1; i < n; ++i) {
		scanf("%d %d", &u, &v);
		addedge(u, v);
		addedge(v, u);
	}
	dfs(1, 0);
	printf("%d\n", f[1][lim]);
	return 0;
}

100分代码
鬼知道是这种优化！！！
背包范围按 $min(size, lim)$ 枚举

#include <cstdio>
#include <cstring>
#include <queue>

using namespace std;

const int N = 123, MOD = 1000000009, INF = 0x3f3f3f3f;
int a[N][N];
int head[N*N], ver[N*N*N], wei[N*N*N], nex[N*N*N], tot;
inline void addedge(int u, int v, int w) {
	ver[tot] = v, wei[tot] = w, nex[tot] = head[u], head[u] = tot++;
}

struct node{
	int x, d;
	node() {}
	node(int X, int DIS) : x(X), d(DIS) {}
	bool operator < (const node& o) const { return d < o.d; }
};
priority_queue<node> q;
int dis[N*N], f[N*N];
void dij() {
	memset(dis, INF, sizeof(dis));
	memset(f, 0, sizeof(f));
	dis[1] = a[1][1]; f[1] = 1;
	q.push(node(1, dis[1]));
	while(!q.empty()) {
		node cur = q.top(); q.pop();
		if(-cur.d > dis[cur.x]) continue;
		for(int i = head[cur.x]; ~i; i = nex[i])
			if(dis[ver[i]] > dis[cur.x] + wei[i]) {
				dis[ver[i]] = dis[cur.x] + wei[i];
				f[ver[i]] = f[cur.x];
				q.push(node(ver[i], -dis[ver[i]]));
			} else if(dis[ver[i]] == dis[cur.x] + wei[i]) {
				f[ver[i]] = (f[cur.x] + f[ver[i]]) % MOD;
			}
				
	}
}

int main() {
	int n;
	while(~scanf("%d", &n) && n) {
		for(int i = 1; i <= n; ++i)
			for(int j = 1; j <= n; ++j) {
				scanf("%d", &a[i][j]);
				if(j > n+1-i) a[n+1-j][n+1-i] += a[i][j];
			}
		memset(head, -1, sizeof(head));
		tot = 0;
		for(int i = 1; i <= n; ++i)
			for(int j = 1; j <= n+1-i; ++j) {
					int cur = (i-1)*n+j;
					if(j != 1) addedge(cur, cur-1, a[i][j-1]);
					if(j != n+1-i) addedge(cur, cur+1, a[i][j+1]), addedge(cur, cur+n, a[i+1][j]);
					if(i != 1) addedge(cur, cur-n, a[i-1][j]);
					if(i+j == n+1) addedge((i-1)*n+j, 0, 0);
				}
		dij();
		printf("%d\n", f[0]);
	}
	return 0;
}

问题：细节方面很不小心,T2存图的表头开小直接TLE丢掉80分
T3认为复杂度不对就没打优化,还是要敢试
T1RE可能也不是特别出乎意料吧,毕竟拍都懒得拍了
就这样漏洞百出我竟然还敢提前48分钟交卷
总的来说应当更加仔细
应该拍大数据(雾)
考场上最后的时间要留出来检查表头有没有开够,以及一些初始化的细节
还是考挂了自己菜,要多加油了

寒鸽儿のBlog

题解 [XJOI] CSP-S2开放一

T1

T2

T3

题解 luoguP1379 八数码难题