D2
今天的题感觉还是好妙的
T1
Description
现在有一张(n)个节点(m)条边的无向连通图(G=(V,E))，满足这张图中不存在长度大于等于3的环且图中没有重边和自环。
定义两个点(u,v)的距离(d(u,v))为这两个点之间最短路上的点数，求
Input
第一行两个正整数n,m，表示点数边数
接下来(m)行，每行两个正整数，描述一条无向边
Output
一行一个整数代表答案。
Sample Input
7 6
1 2
1 6
2 5
3 1
4 7
2 4
Sample Output
3
Hint
(For~All:)
(n,m~leq~10^5)
(For~30~percent:)
(n,m~leq~20)
(For~60~percent:)
(n,m~leq~1000)
Solution
考虑这个十分煞笔的描述……其实这是棵树
题意是让你找到一个点，使得这个点到最远的点的距离最小
考虑30分做法，直接Floyd即可
考虑60分做法……我不知道60分怎么做
考虑100做法。一个点像最远的点的路径只有可能有两种情况，分别是向上走和向下走的两种情况于是可以先一遍dfs确定一个点向下的最长路，然后树形DP求出这个点的最长路。具体的，对每个节点维护最长路和次长路，无需严格次长，同时维护分别是从哪里转移。显然根节点的最长路是向下的。对于一个非根节点，如果它的父亲的最长路是转移向他的，那么将它的最长路即为父亲的次长路，否则记为最长路。然后枚举这个节点的子节点，求出他向下的最长路，进行转移。至此这个节点的最长路与次长路已经被全部求出，然后可以枚举他的子节点向子节点转移。
hjc说这是个结论题。可我觉得这就是个树形DP吖？
Code
#include<cstdio>
#define rg register
#define ci const int
#define cl const long long int
namespace IO {
char buf[110];
}
template <typename T>
inline void qr(T &x) {
char ch=getchar(),lst=' ';
while((ch > '9') || (ch < '0')) lst=ch,ch=getchar();
while((ch >= '0') && (ch <= '9')) x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
if(lst == '-') x=-x;
}
template <typename T>
inline void write(T x,const char aft,const bool pt) {
if(x < 0) {putchar('-');x=-x;}
rg int top=0;
do {
IO::buf[++top]=x%10+'0';x/=10;
} while(x);
while(top) putchar(IO::buf[top--]);
if(pt) putchar(aft);
}
template <typename T>
inline T mmax(const T a,const T b) {return a > b ? a : b;}
template <typename T>
inline T mmin(const T a,const T b) {return a < b ? a : b;}
template <typename T>
inline T mabs(const T x) {return x < 0 ? -x : x;}
template <typename T>
inline void mswap(T &a,T &b) {
T temp=a;a=b;b=temp;
}
const int maxn = 100010;
const int maxm = 200010;
struct Edge {
int to,nxt;
};
Edge edge[maxm];int hd[maxn],ecnt;
inline void cont(ci from,ci to) {
Edge &e=edge[++ecnt];
e.to=to;e.nxt=hd[from];hd[from]=ecnt;
}
int n,m,ans=0x3f3f3f3f;
int fa[maxn],frog[maxn][3],md[maxn],pre[maxn];
void DFS(ci);
void reading();
void dfs(ci,ci);
int main() {
freopen("distance.in","r",stdin);
freopen("distance.out","w",stdout);
qr(n);qr(m);
reading();
dfs(1,0);
DFS(1);
write(ans,'
',true);
return 0;
}
void reading() {
rg int a,b;
while(m--) {
a=b=0;qr(a);qr(b);
cont(a,b);cont(b,a);
}
}
void dfs(ci u,ci fat) {
fa[u]=fat;
for(rg int i=hd[u];i;i=edge[i].nxt) {
int &to=edge[i].to;
if(to == fat) continue;
dfs(to,u);
md[u]=mmax(md[u],md[to]);
}
++md[u];
}
void DFS(ci u) {
if(pre[fa[u]] != u) frog[u][1]=frog[fa[u]][1]+1;
else frog[u][1]=frog[fa[u]][2]+1;
pre[u]=fa[u];
for(rg int i=hd[u];i;i=edge[i].nxt) {
int &to=edge[i].to;
if(to == fa[u]) continue;
if(frog[u][1] < (md[to]+1)) frog[u][2]=frog[u][1],frog[u][1]=md[to]+1,pre[u]=to;
else if(frog[u][2] < (md[to]+1)) frog[u][2]=md[to]+1;
}
for(rg int i=hd[u];i;i=edge[i].nxt) {
int &to=edge[i].to;
if(to == fa[u]) continue;
DFS(to);
}
ans=mmin(ans,frog[u][1]);
}
T2
Description
给你一张(n)个点(m)条边的无向图，每条边有一个权值(w_i)。
求一条(S)到(T)的路径，使得这条路上权值最大的边比权值最小的边比值最小
Input
第一行是两个正整数(n,m)，代表图的点数和边数
接下来的(m)行每行三个正整数(x,y,w)，代表一条权值为(w)的边
最后一行两个正整数(S,T)
Output
如果(S)到(T)不连通输出(IMPOSSIBLE)，否则输出答案
答案形如一个A/B的既约分数
Hint
(For~All:)
(1~leq~n~leq~500,1~leq~m~leq~5000,1~leq~w~leq~30000,x~ eq~y,S~ eq~T)
(For~20~percents:)
(n,m~leq~5)
(For~other~30~percents:)
(n~leq~100,m~leq~200,w~leq~100)
Solution
考虑前20分可以暴力枚举选哪些边
剩下30分做法，考虑所有的元素都只有几百，于是可以使用bool型DP来做这道题。
可以设(f_{i,j,k}=true/false)代表从(S)到点(i)，是否存在一个最大值为(j)，最小值是(k)的路径。转移我不会。
我的做法是two points乱搞。考虑枚举最小的边，然后发现最小的边权单调不降时，最大的边权也单调不降。于是可以(Two~points)省掉最大边权的枚举。每次指针移动时暴力bfs判断连通性。于是复杂度(O(m^2))，其实就A了。然而我数组开小了，于是挂了50
考虑std的满分做法。发现边依然可以枚举。于是考虑枚举最小的边，发现问题等价于求一个最小瓶颈路。然后枚举最小边求暴力克鲁斯卡尔就可以AC。
Code
这代码写的可真丑
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
using namespace std;
const int N = (int)1e4;
typedef int arr[N + 10];
int n, m, S, T;
arr ufs;
int bestnum, bestdenom;
struct edge {
int x, y, w;
}e[N + 10];
int find(int x) { return ufs[x] == x ? x : ufs[x] = find(ufs[x]); }
int gcd(int x, int y) { return y == 0 ? x : gcd(y, x % y); }
bool cmp(const edge &a, const edge &b) { return a.w < b.w; }
int main() {
freopen("graph.in", "r", stdin);
freopen("graph.out", "w", stdout);
scanf("%d %d", &n, &m);
for (int i = 1; i <= m; ++i) scanf("%d %d %d", &e[i].x, &e[i].y, &e[i].w);
scanf("%d %d", &S, &T);
sort(e + 1, e + m + 1, cmp);
bestnum = 30001, bestdenom = 1;
for (int i = 1; i <= m; ++i) {
for (int j = 1; j <= n; ++j) ufs[j] = j;
int j = i;
for ( ; j <= m; ++j) {
int fx = find(e[j].x), fy = find(e[j].y);
if (fx != fy) ufs[fx] = fy;
if (find(S) == find(T)) break;
}
if (find(S) == find(T)) {
if (e[j].w * bestdenom < e[i].w * bestnum)
bestnum = e[j].w, bestdenom = e[i].w;
}
}
if (bestnum == 30001) printf("IMPOSSIBLE
");
else {
int g = gcd(bestnum, bestdenom);
bestnum /= g, bestdenom /= g;
if (bestdenom == 1) printf("%d
", bestnum);
else printf("%d/%d
", bestnum, bestdenom);
}
return 0;
}
T3
Description
有一个小学生去买糖，商店中共有n种不同的糖果，其中每一种糖果有两种选择：大糖果和小糖果各自只有一个，并且各自有一个价格。满足大糖果一定比小糖果贵。对于任意一种糖果，大糖果给小学生带来的愉悦度是2，小糖果给小学生带来的愉悦度是1。由于小学生不喜欢口味相同的糖果，所以对于一种糖果，他不会同时买大糖果和小糖果。
现在小朋友想要获得P点愉悦度，但花费最少的钱。请你帮帮他。
Input
第一行两个整数(n,p)
接下来(n)行，每行两个整数(a_i)和(b_i)，表示第(i)种糖果小糖果和大糖果的价格。
Output
共输出(n+1)行。
第一行输出最小花费
对于(i~in~[2,n+1])，第(i)行输出第(i-1)种糖果买大买小还是不买。不买输出(0),买小输出(1),买大输出(2)。如果有多种方案，那你就凉了。因为我不会写spj
Hint
(For~All:)
(n~leq~2~ imes~10^5,a_i~le~b_i,p~leq~2~ imes~n,b_i~leq~2^21-1)
(For~30~percents:)
(n~leq~10)
(For~other~20~percents:)
(n~leq~1000,1~leq~a_i~leq~10~,~100~leq~b_i~leq~1000)
Solution
显然可以DP。这样可以拿50分。
考虑贪心。
另外20分的做法。题目给定了(a_i~ imes~2~<~b_i)
于是把两个糖果改为两个贡献都是(1)的，价格分别是(a_i)和(b_i-a_i)，于是按照价格排序直接排序贪心。因为(a_i)显然小于(b_i-a_i)，于是选了后者的时候一定选择了前者。贪心正确
考虑正解
于是就完了