EC Final西安赛前恢复性训练

2019-04-14 15:28发布生成海报

站内文章 / 模拟电子

16549 0

回老乡打EC可还行缘分啊... 开始一些针对性的恢复性训练吧。从2018.12.6开始训练7天。 DAY1 搜索相关 Luogu 1101 本来想写AC自动机后来觉得还是写搜索简单点，AC自动机过几天再练吧。

#include 
#include 
#include 
using namespace std;

const int dx[9] = {0, 0, 1, 0, -1, 1, 1, -1, -1};
const int dy[9] = {0, 1, 0, -1, 0, 1, -1, 1, -1};
const char stand[8] = "yizhong";

int N;
char map[200][200];
bool vis[200][200];

inline void dfs(int x, int y, int dir, int depth) {
	if(depth == 7) {
		for(int i = 1; i <= 7; ++i) 
			vis[x - i * dx[dir]][y - i * dy[dir]] = true;
		return;
	}
	else {
		int nx = x + dx[dir], ny = y + dy[dir];
		if(depth == 6 || map[nx][ny] == stand[depth + 1]) {
			dfs(nx, ny, dir, depth + 1);
		}
	}
}

int main() {
	scanf("%d", &N);
	for(int i = 0; i < N; ++i) scanf("%s", map[i]);
	for(int i = 0; i < N; ++i) for(int j = 0; j < N; ++j) {
		if(map[i][j] == 'y') {
			for(int k = 1; k <= 8; ++k) {
				int x = i + dx[k], y = j + dy[k];
				if(map[x][y] == 'i') dfs(i, j, k, 0);
			}
		}
	}
	for(int i = 0; i < N; ++i) {
		for(int j = 0; j < N; ++j) {
			if(vis[i][j]) printf("%c", map[i][j]);
			else printf("*");
		}
		printf("
");
	}
	return 0;
}

POJ 3083 DFS+BFS 代码题 5k的代码出题人我CNM

#include 
#include 
#include 
#include 
#include 
using namespace std;
// 上1 左2 下3 右4

const int dx[5] = {0, 0, 1, 0, -1};
const int dy[5] = {0, 1, 0, -1, 0};

struct node {
    int x, y;
    int step;
};

int W, H, ansleft, ansright;
node st, ed;
char map[50][50];
bool vis[50][50];


inline bool check(int x, int y) {
    if(x >= 0 && x < H && y >= 0 && y < W && map[x][y] != '#') return true;
    else return false;
}

void init() {
	ansleft = 0, ansright = 0;
	memset(vis, false, sizeof(vis));
}

void dfs_left(int x, int y, int dir) {
    ++ansleft;
    if(x == ed.x && y == ed.y) return;

    switch(dir) {
        case 1: {
            if(check(x, y - 1)) dfs_left(x, y - 1, 2);
            else if(check(x - 1, y)) dfs_left(x - 1, y, 1);
            else if(check(x, y + 1)) dfs_left(x, y + 1, 4);
            else if(check(x + 1, y)) dfs_left(x + 1, y, 3);
            break;
        }

        case 2: {
            if(check(x + 1, y)) dfs_left(x + 1, y, 3);
            else if(check(x, y - 1)) dfs_left(x, y - 1, 2);
            else if(check(x - 1, y)) dfs_left(x - 1, y, 1);
            else if(check(x, y + 1)) dfs_left(x, y + 1, 4);
            break;
        }

        case 3: {
            if(check(x, y + 1)) dfs_left(x, y + 1, 4);
            else if(check(x + 1, y)) dfs_left(x + 1, y, 3);
            else if(check(x, y - 1)) dfs_left(x, y - 1, 2);
            else if(check(x - 1, y)) dfs_left(x - 1, y, 1);
            break;
        }

        case 4: {
            if(check(x - 1, y)) dfs_left(x - 1, y, 1);
            else if(check(x, y + 1)) dfs_left(x, y + 1, 4);
            else if(check(x + 1, y)) dfs_left(x + 1, y, 3);
            else if(check(x, y - 1)) dfs_left(x, y - 1, 2);
            break;
        }
    }

    return;
}

void dfs_right(int x, int y, int dir) {
    ++ansright;
    if(x == ed.x && y == ed.y) return;

    switch(dir) {
        case 1: {
            if(check(x, y + 1)) dfs_right(x, y + 1, 4);
            else if(check(x - 1, y)) dfs_right(x - 1, y, 1);
            else if(check(x, y - 1)) dfs_right(x, y - 1, 2);
            else if(check(x + 1, y)) dfs_right(x + 1, y, 3);
            break;
        }

        case 2: {
            if(check(x - 1, y)) dfs_right(x - 1, y, 1);
            else if(check(x, y - 1)) dfs_right(x, y - 1, 2);
            else if(check(x + 1, y)) dfs_right(x + 1, y, 3);
            else if(check(x, y + 1)) dfs_right(x, y + 1, 4);
            break;
        }

        case 3: {
            if(check(x, y - 1)) dfs_right(x, y - 1, 2);
            else if(check(x + 1, y)) dfs_right(x + 1, y, 3);
            else if(check(x, y + 1)) dfs_right(x, y + 1, 4);
            else if(check(x - 1, y)) dfs_right(x - 1, y, 1);
            break;
        }

        case 4: {
            if(check(x + 1, y)) dfs_right(x + 1, y, 3);
            else if(check(x, y + 1)) dfs_right(x, y + 1, 4);
            else if(check(x - 1, y)) dfs_right(x - 1, y, 1);
            else if(check(x, y - 1)) dfs_right(x, y - 1, 2);
            break;
        }
    }

    return;
}

int bfs() {
    queue Q;
    Q.push((node){st.x, st.y, 1});
    vis[st.x][st.y] = true;
    
    while(!Q.empty()) {
        node now = Q.front(); Q.pop();
        if(now.x == ed.x && now.y == ed.y) return now.step;
        for(int i = 1; i <= 4; ++i) {
        	int nx = now.x + dx[i], ny = now.y + dy[i], nstep = now.step + 1;
        	if(nx < 0 || nx > H || ny < 0 || ny > W || vis[nx][ny]) continue;
        	if(map[nx][ny] != '#') {
           		vis[nx][ny] = true;
            	Q.push((node){nx, ny, nstep});
        	}
		} 
    }
    
    return -1;
}

int main() {
    int T; scanf("%d", &T);

    while(T--) {
        int dir;  // 上1 左2 下3 右4
        scanf("%d%d", &W, &H);
        init();
        for(int i = 0; i < H; ++i) scanf("%s", map[i]);
        for(int i = 0; i < H; ++i) for(int j = 0; j < W; ++j) {
            if(map[i][j] == 'S') {
                st.x = i, st.y = j;
                if(i == H - 1) dir = 1;  // 上 
                if(j == W - 1) dir = 2;  // 左 
                if(i == 0) dir = 3;  // 下 
                if(j == 0) dir = 4;  // 右 
            }

            if(map[i][j] == 'E') ed.x = i, ed.y = j;
        }

        switch(dir) {  // 左优先搜索 
            case 1: { dfs_left(st.x - 1, st.y, 1); break; }
            case 2: { dfs_left(st.x, st.y - 1, 2); break; }
            case 3: { dfs_left(st.x + 1, st.y, 3); break; }
            case 4: { dfs_left(st.x, st.y + 1, 4); break; }
        }
        printf("%d ", ansleft + 1);

        switch(dir) {  // 右优先搜索 
            case 1: { dfs_right(st.x - 1, st.y, 1); break; }
            case 2: { dfs_right(st.x, st.y - 1, 2); break; }
            case 3: { dfs_right(st.x + 1, st.y, 3); break; }
            case 4: { dfs_right(st.x, st.y + 1, 4); break; }
        }
        printf("%d ", ansright + 1);

        printf("%d
", bfs());
    }
    return 0;
}

DAY2 图论相关 POJ 3169 差分约束系统但是这道题网上题解几乎全灭包括LUOGU的官方题解以及CSDN最高浏览量的题解他们的问题在于这组数据 5 1 1 1 5 10 2 3 20 由于题面上说明了奶牛按序号排列，那么就应该满足差分约束系统中D[i + 1] + 0 >= D[i] 也就是说我们需要连接相邻两边来判断答案是否合法以及CSDN那个题解还存在一个问题是没有判断图的连通性怪就怪POJ的数据太水 LUOGU4878的数据能好一些但依然没有卡住我说的第一个点

#include 
#include 
#include 
#include 
#include 
using namespace std;

const int MAXN = 1000 + 10;
const int MAXM = 40000 + 10;

inline int read() {
    int x = 0, f = 1; char ch = getchar();
    while(ch < '0' || ch > '9') { if(ch == '-') f = -1; ch = getchar(); }
    while(ch >= '0' && ch <= '9') { x = x * 10 + ch - '0'; ch = getchar(); }
    return x * f;
}

struct data { int to, next, w; }edge[MAXM];
int N, ML, MD, head[MAXN], cnt;
int dis[MAXN], negative_loop[MAXN];
bool vis[MAXN];

inline void addedge(int u, int v, int w) {
    edge[++cnt].to = v; edge[cnt].next = head[u];
    edge[cnt].w = w; head[u] = cnt;
}

void SPFA(int st) {
    memset(dis, 0x3f3f3f3f, sizeof(dis));
    memset(vis, false, sizeof(vis));
    memset(negative_loop, 0, sizeof(negative_loop));
    queue Q; Q.push(st);
    vis[st] = true; dis[st] = 0;

    while(!Q.empty()) {
        int now = Q.front(); Q.pop();
        vis[now] = false;
        for(int i = head[now]; i; i = edge[i].next) {
            int w = edge[i].w, son = edge[i].to;
            if(dis[now] + w < dis[son]) {
                dis[son] = dis[now] + w;
                negative_loop[son] = negative_loop[now] + 1;
                if(negative_loop[son] >= N) {
                    puts("-1");
                    exit(0);
                }
                if(!vis[son]) {
                    Q.push(son);
                    vis[son] = true;
                }
            }
        }
    }
}

int main() {
    N = read(), ML = read(), MD = read();
    for(int i = 1; i <= N; ++i) addedge(0, i, 0);
    for(int i = 1; i <= N - 1; ++i) addedge(i + 1, i, 0);
    for(int i = 1, u, v, w; i <= ML; ++i) {
        u = read(), v = read(), w = read();
        if(v < u) swap(u, v);
        addedge(u, v, w);
    }
    for(int i = 1, u, v, w; i <= MD; ++i) {
        u = read(), v = read(), w = read();
        if(v < u) swap(u, v);
        addedge(v, u, -w);
    }
    SPFA(0); SPFA(1);
    if(dis[N] == 0x3f3f3f3f) puts("-2");
    else printf("%d
", dis[N]);
    return 0;
}

DAY3 POJ炸了 DAY4 早上完成了2017ECfinal模拟训练 POJ 2728 最优比率生成树

#include 
#include 
#include 
#include 
#include 
using namespace std;

const int inf = 0x3f3f3f3f;
const double eps = 1e-7;
const int MAXN = 1000 + 10;

int N;
double benefit[MAXN][MAXN], cost[MAXN][MAXN];
double value[MAXN][MAXN], mincost[MAXN];
bool used[MAXN];

struct point {
    int x, y, z;
}village[MAXN];

inline int read() {
    int x = 0, f = 1; char ch = getchar();
    while(ch < '0' || ch > '9') { if(ch == '-') f = -1; ch = getchar(); }
    while(ch >= '0' && ch <= '9') { x = x * 10 + ch - '0'; ch = getchar(); }
    return x * f;
}

double cal_dist(int i, int j) {
    return sqrt((village[i].x - village[j].x) * (village[i].x - village[j].x) + (village[i].y - village[j].y) * (village[i].y - village[j].y));
}

double prim(double r) {
    for(int i = 1; i <= N; ++i) for(int j = i; j <= N; ++j) {
        value[i][j] = benefit[i][j] - r * cost[i][j];
        value[j][i] = value[i][j];
        if(i == j) value[i][j] = (double)0x3f3f3f3f;
    }
    for(int i = 1; i <= N; ++i) {
        mincost[i] = (double)0x3f3f3f3f;
        used[i] = false;
    }
    mincost[1] = 0; double res = 0;

    while(1) {
        int v = -1;
        for(int u = 1; u <= N; ++u) {
            if(!used[u] && (v == -1 || mincost[u] < mincost[v])) v = u;
        }
        if(v == -1) break;
        used[v] = true;
        res += mincost[v];
        for(int u = 1; u <= N; ++u) {
            mincost[u] = min(mincost[u], value[v][u]);
        }
    }
    return res;
}


int main() {
    while(scanf("%d", &N) == 1  && N) {
        for(int i = 1, u, v, w; i <= N; ++i) {
            u = read(), v = read(), w = read();
            village[i] = (point){u, v, w};
        }

        double l = 0, r = 10;
        for(int i = 1; i <= N; ++i) for(int j = i; j <= N; ++j) {
            benefit[i][j] = abs(village[i].z - village[j].z);
            benefit[j][i] = benefit[i][j];
            cost[i][j] = cal_dist(i, j);
            cost[j][i] = cost[i][j];
            r += benefit[i][j];
        }

        while(r - l > eps) {
            double mid = (l + r) / 2.0;
            if(prim(mid) >= 0) l = mid;
            else r = mid;
        }
        printf("%.3f
", l);
    }
    return 0;
}

WA了一整天最后无奈下把最终输出的lf改成了f 就AC了？？

EC Final西安赛前恢复性训练

Ta的文章更多 >>

热门文章

EC Final西安赛前恢复性训练

Ta的文章 更多 >>

热门文章

举报内容

检举类型

检举原因

检举说明(必填)

打开微信“扫一扫”，打开网页后点击屏幕右上角分享按钮

Ta的文章更多 >>