首页 > 代码库 > Codeforces449A Jzzhu and Chocolate && 449B Jzzhu and Cities

Codeforces449A Jzzhu and Chocolate && 449B Jzzhu and Cities

2024-07-12 23:29:57   221人阅读

CF挂0了，简直碉堡了。两道题都是正确的思路但是写残了。写个解题报告记录一下心路历程。

A题问的是 一个n*m的方块的矩形上切k刀，最小的那一块最大可以是多少。不难发现如果纵向切k1刀，横向切k2刀，那么答案应该是 (n/(k1+1)) * (m/(k2+1)),除法是取整的。虽然是取整，但是不难发现其实就是要(k1+1)*(k2+1)最小，根据均值不等式，k1+k2=k(定值) k1==k2的时候(k1+1)*(k2+1)＝k1*k2+k1+k2+1=k1*k2+k+1应该是取最大值，所以当k1,k2越接近两端的时候这个值才会最小，所以我们总是先把某一维的切掉，然后再考虑剩下那一维。比赛的时候手残写错了，哎。。。

B题问的是给你一个图，一些是普通边，一些是train route边，train route边是从首都1连到其它点的，问的是train route边最多可以去掉多少条使得每个点的最短路径长不变。思路就是如果某个点我们可以通过走别的点到达的话，那么这条边是不需要的，留边的时候更新ans我写漏了，导致答案小了很多。

#pragma warning(disable:4996)#include <iostream>#include <cstdio>#include <vector>#include <cstring>#include <string>#include <algorithm>#include <cmath>#include <queue>using namespace std;#define ll long long#define maxn 105000#define inf 10000000000000000LLint n, m, k;struct Edge{	int v;	ll w;	Edge(int vi, ll wi) : v(vi), w(wi){}	Edge(){}};vector<Edge>G[maxn];ll dis2[maxn];ll ans = 0;ll d[maxn];bool in[maxn];void spfa(){	memset(d, 0x3f, sizeof(d));	memset(in, 0, sizeof(in));	queue<int> que;	que.push(1); in[1] = true;	d[1] = 0;	while (!que.empty()){		int u = que.front(); que.pop(); in[u] = false;		for (int i = 0; i < G[u].size(); i++){			int v = G[u][i].v; ll w = G[u][i].w;			if (d[u] + w < d[v]){				d[v] = d[u] + w;				if (!in[v]) que.push(v), in[v] = true;			}		}	}}ll d2[maxn];bool upd[maxn];void spfa2(){	memset(d2, 0x3f, sizeof(d2));	memset(in, 0, sizeof(in));	queue<int> que;	que.push(1); d2[1] = 0; in[1] = true;	for (int i = 2; i <= n; i++){		if (dis2[i] < d[i]){			que.push(i); in[i] = true; d2[i] = dis2[i];		}	}	while (!que.empty()){		int u = que.front(); que.pop(); in[u] = false;		for (int i = 0; i < G[u].size(); i++){			int v = G[u][i].v; ll w = G[u][i].w;			if (d2[u] + w < d2[v]){				d2[v] = d2[u] + w;				if (!in[v]) que.push(v), in[v] = true;				if (upd[v]) {					++ans; upd[v] = false;				}			}			else if (d2[u] + w == d2[v]){				if (upd[v]) {					++ans; upd[v] = false;				}			}		}	}}int main(){	while (cin >> n >> m >> k){		for (int i = 0; i <= n; i++) G[i].clear();		memset(dis2, 0x3f, sizeof(dis2));		ans = 0;		int ui, vi; ll wi;		for (int i = 0; i < m; i++){			scanf("%d%d%I64d", &ui, &vi, &wi);			G[ui].push_back(Edge(vi, wi));			G[vi].push_back(Edge(ui, wi));		}		spfa();		memcpy(dis2, d, sizeof(dis2));		memset(upd, 0, sizeof(upd));		int si; ll yi;		for (int i = 0; i < k; i++){			scanf("%d%I64d", &si, &yi);			if (dis2[si] <= yi) ++ans;			else {				dis2[si] = yi; 				if (upd[si]) {					++ans;				}				upd[si] = true;			}		}		spfa2();		cout << ans << endl;	}	return 0;}


联系
我们