A
看样例猜做法
首先看看题目思索几秒应该和差分数组有关
然后拿差分数组试了一下样例, 猜了一个做法
再自己构造了一下数据, 好像是可以过的样子
对拍对拍! 哦豁我不会写暴力啊 orz, 还好没出错 orzorzorz, 不过评测的时候着实有点慌
B
一开始没看题面, 以为是一个面值拿其他俩面值表示就可以了, 想了想, 对! EX_gcd, 敲了 30~40min, 小样例过了, 大样例过过过过... 唉握草??! 最后一个点怎么回事
哎握草??!!!! 它一个数是拿另外三个数表示的!!!
我人傻了. JPEG
最后才想起来, 它是背包啊是背包, 还是最简单的那种无限背包 (背包问题 1.......),f 数组甚至是 bool 类型的那种背包
C
emmm, 没啥想法的一道题
方法过于难以描述, 将在最后放上代码, 其中上下均 /////// 的表示在写题中没有注意到的错误 (还挺多的)
老板说的对, 这道题满分不好拿, 但是由于数据分段给的非常清楚, 要混上个 40,50 分是轻轻松松的, 而我 WA0 确实是不应该 (随便敲一个树的直径都有 20 分)
总结一下
期望得分:\(100 + 100 +0 = 200\)
实际得分:\(100 + 100 + 0 = 200\)
没有什么大的智障失误, 不过 WA0 是非常不应该的
最后放上 C 题 AC 代码
- #include<stdio.h>
- #include<bits/stdc++.h>
- #define LL long long
- #define maxn 50005
- #define maxm 100005
- #define rel(i,s,n) for(int i=(s);i<(n);i++)
- #define rep(i,s,n) for(int i=(s);i<=(n);i++)
- #define red(i,s,n) for(int i=(s);i>=(n);i--)
- #define res(i,x) for(int i=Last[x];i;i=Next[i])
- using namespace std;
- char buf[1<<20],*p1,*p2;
- #define GC (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<20,stdin),p1==p2)?0:*p1++)
- template<class T> inline void read(T &n){
- char ch=GC;T w=1,x=0;
- while(!isdigit(ch)){if(ch=='-') w=-1;ch=GC;}
- while(isdigit(ch)){x=(x<<3)+(x<<1)+(ch^48);ch=GC;}
- n=x*w;
- }
- int x,y,z;
- int L,R,Mid;
- int n,m,tot,Ans;
- struct Phenning{int id;int val;bool MK;};
- int End[maxm],Last[maxn],Next[maxm],Len[maxm],f[maxn],g[maxn];
- vector<Phenning>Son[maxn];
- bool cmp(Phenning a, Phenning b){
- return a.val <b.val;
- }
- void add(int x, int y, int z){
- tot ++;
- Next[tot] = Last[x];
- Last[x] = tot;
- End[tot] = y;
- Len[tot] = z;
- }
- void QwQ(int x, int fa){
- int son = 0;
- res(i,x)if(End[i]!=fa){
- son ++;
- QwQ(End[i], x);
- ///////////////!!!!!!!!!!!!!!!!!!!!!
- f[x]+=f[End[i]];
- ///////////////!!!!!!!!!!!!!!!!!!!!!
- Phenning tmp;
- tmp.MK = 0;
- tmp.id = End[i];
- tmp.val = Len[i] + g[End[i]];
- Son[x].push_back(tmp);
- }
- if(son == 0)return;
- son --;
- sort(Son[x].begin(), Son[x].end(), cmp);
- rep(i, 0, son)if(Son[x][i].val>= Mid){f[x] ++; Son[x][i].MK = 1; continue;}
- rep(i, 0, son){
- //////////////////////////
- if(Son[x][i].MK) continue;
- //////////////////////////
- Phenning tmp;
- tmp.val = Mid - Son[x][i].val;
- int pos = lower_bound(Son[x].begin()+i+1, Son[x].end(), tmp, cmp) - Son[x].begin();
- if(pos>son)continue;
- while(Son[x][pos].MK == 1 && pos <son)pos ++;
- ///////////////////////////
- if(Son[x][pos].MK == 1)continue;
- ///////////////////////////
- if(Son[x][pos].val>= tmp.val){f[x] ++; Son[x][i].MK = Son[x][pos].MK = 1;}
- }
- red(i, son, 0)if(!Son[x][i].MK){g[x] = Son[x][i].val;break;}
- ///////////////
- Son[x].clear();
- ///////////////
- }
- bool isok(){
- rep(i, 1, n)f[i] = g[i] = 0;
- QwQ(1, 0);
- if(f[1]>= m)return 1;
- //puts("hahhahaha");
- return 0;
- }
- int main(){
- read(n);read(m);
- rel(i, 1, n){
- read(x);read(y);read(z);
- R += z;
- add(x, y, z);
- add(y, x, z);
- }
- while(L <= R){
- Mid = (L + R)>> 1;
- if(isok())Ans = Mid, L = Mid + 1;
- else R = Mid - 1;
- }
- printf("%d", Ans);
- return 0;
- }
- // 长度最小的赛道长度最大: 二分
来源: http://www.bubuko.com/infodetail-3224386.html