| A | 鲲 |
时间限制：C/C++ 1秒，其他语言2秒
空间限制：C/C++ 262144K，其他语言524288K
64bit IO Format: %lld
题目描述
北冥有鱼，其名为鲲，鲲之大，不知其几千里也。
——《庄子·逍遥游》
HtBest有一条可爱的小鲲，HtBest想和与小鲲比赛游泳，我们可以把游泳池看成一个圆环，两人从起点游一圈回到起点即可完成比赛。两人在距离小于k时（距离指的是在环上的距离，而非直线距离），他们会互相监督对方有没有全速向前游，如果发现有一方没有全速向前游，则视为作弊，聪明的HtBest为了省力（更为了赢得比赛），可以选择在两者相距超过k的时候，立马掉头反向游以更快到达起点，HtBest想让你求出小鲲最少比HtBest提前多长时间完成比赛。（若HtBest比小鲲先完成比赛，输出负数）
说明：小鲲不会作弊。
输入描述:
一行，包含四个正整数，两两之间用空格分开：L(游泳池周长)、k(互相监督距离)、a(小鲲速度)、b(HtBest速度)。
所有输入数据均不超过1e9。输出描述:
一行，包含一个数，表示小鲲最少比HtBest提前多长时间完成比赛。（保留两位小数）。
示例1
输入
复制
4 3 2 1输出
复制
2.00说明
小鲲用时4/2=2，HtBest用时4/1=4，4-2=2。示例2
输入
复制
10 2 3 1输出
复制
-1.33说明
出发1单位时间后，小鲲跑了3，HtBest跑了1，此时互相监督无效，HtBest作弊反向游，第2单位时间后，HtBest游回终点，小鲲用时10/3=3.33，2-3.33=-1.33。AC:
注意,这是个环,鲲快到终点时与htbest的距离可能小于k,呢个时候htbest不可以往回走
#include<cstdio>
#include<iostream>
#include<cstring>
using namespace std;int main()
{int l,k,a,b;double t1,t2,dt;scanf("%d%d%d%d",&l,&k,&a,&b);t1=l*1.0/a;if(a>b){t2=k*1.0/(a-b);if(2*t2<t1&&t2*2<l*1.0/b)dt=2*t2-t1;else dt=l*1.0/b-t1;printf("%.2f\n",dt);}else printf("%.2f\n",l*1.0/b-t1);return 0;
}| B | 鹏 |
时间限制：C/C++ 2秒，其他语言4秒
空间限制：C/C++ 262144K，其他语言524288K
64bit IO Format: %lld
题目描述
化而为鸟，其名为鹏。鹏之背，不知其几千里也。
——《庄子·逍遥游》
HtBest的小鲲长大变成了大鹏，大鹏在天际翱翔，看到了一片绵延的山脉，每座山都有自己的高度，大鹏想穿过这片山脉。由于他只能紧贴地面飞行，他想知道他一共要翻越几次大山（上升->平飞->下降，算一次，其中平飞可以没有），初始时，大鹏在山脉的左端。
输入描述:
第一行一个正整数n，表示山脉被分为n段。
第二行有n个正整数ai两两之间用空格分开，ai表示山脉第i段的高度。输出描述:
一行，包含一个正整数，表示大鹏需要翻越几次大山。
示例1
输入
复制
3
1 2 1 输出
复制
1说明
大鹏先上升一次，再下降一次，共翻越1次。示例2
输入
复制
3
3 1 2输出
复制
0说明
大鹏先下降一次，再上升一次，共翻越0次。示例3
输入
复制
3
1 2 3直接简单处理,注意ai会大于int,要用long long
AC:
#include<cstdio>
#include<cstring>
using namespace std;int main()
{int n,flag,sum;long long x,y;sum=flag=0,y=-1;scanf("%d",&n);for(int i=0;i<n;i++){scanf("%lld",&x);if(i){if(x>y)flag=1;else if(x<y&&flag)flag=0,sum++;}y=x;}printf("%d\n",sum);return 0;
}| C | 桃花 |
时间限制：C/C++ 1秒，其他语言2秒
空间限制：C/C++ 262144K，其他语言524288K
64bit IO Format: %lld
题目描述
桃花一簇开无主，可爱深红映浅红。
——《题百叶桃花》
桃花长在桃树上，树的每个节点有一个桃花，调皮的HtBest想摘尽可能多的桃花。HtBest有一个魔法棒，摘到树上任意一条链上的所有桃花，由于HtBest法力有限，只能使用一次魔法棒，请求出Htbest最多可以摘到多少个桃花。
输入描述:
第一行有一个正整数n，表示桃树的节点个数。
接下来n-1行，第i行两个正整数ai,bi ，表示桃树上的节点ai,bi之间有一条边。输出描述:
第一行一个整数，表示HtBest使用一次魔法棒最多可以摘到多少桃花。
示例1
输入
复制
3
1 2
2 3输出
复制
3示例2
输入
复制
3
1 2
1 3输出
复制
3示例3
输入
复制
4
1 2
2 3
3 4输出
复制
4备注:
对于100%的测试数据：
1 ≤ n ≤ 1000000
数据量较大，注意使用更快的输入输出方式。求连通图中最长距离的两点距离,先随便找个点求最长距离点
然后从最长距离点为起点,求最长距离,第二次求到的即是该连通图最长距离,直接两次dfs
我用vector有时候超时,有时候通过,换用链式前向星直接ac;
AC:
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#define maxn 1024000
using namespace std;
int head[2*maxn],cnt,maxs,maxi,vis[2*maxn];struct node
{int u,v,next;
}edge[2*maxn];void add_edge(int u,int v)
{edge[cnt].u=u;edge[cnt].v=v;edge[cnt].next=head[u];head[u]=cnt++;
}void dfs(int x,int sum)
{vis[x]=1;if(sum>maxs)maxs=sum,maxi=x;for(int i=head[x];i!=-1;i=edge[i].next)if(!vis[edge[i].v])dfs(edge[i].v,sum+1);
}int main()
{int n,a,b;memset(head,-1,sizeof(head));memset(vis,0,sizeof(vis));memset(edge,0,sizeof(edge));cnt=0;scanf("%d",&n);for(int i=0;i<n-1;i++){scanf("%d%d",&a,&b);add_edge(a,b);add_edge(b,a);}maxs=-1,maxi=-1;dfs(1,1);memset(vis,0,sizeof(vis));dfs(maxi,1);printf("%d\n",maxs);return 0;
}| H | 挖沟 |
直接用kruskal算法
ac:
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#define maxn 100007
using namespace std;
int n,m,a,b,w;
int f[maxn];struct node
{int a,b,w;
}tree[maxn*5];int cmp(node x,node y)
{return x.w<y.w;
}int find(int x)
{if(x!=f[x])f[x]=find(f[x]);return f[x];
}int mix(int x,int y)
{int fx=find(x),fy=find(y);if(fx!=fy)f[fy]=fx;else return 0;return 1;
}void kru()
{int sum=0,num=0;sort(tree,tree+m,cmp);for(int i=0;i<m&&num!=n-1;i++){if(mix(tree[i].a,tree[i].b)){num++;sum+=tree[i].w;}}printf("%d\n",sum);
}int main()
{memset(tree,0,sizeof(tree));scanf("%d%d",&n,&m);for(int i=0;i<n;i++)f[i]=i;for(int i=0;i<m;i++)scanf("%d%d%d",&tree[i].a,&tree[i].b,&tree[i].w);kru();return 0;
}J:
| 洋灰三角 |
用矩阵快速幂解决,也可以直接公式法解决
ac:
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define P 1000000007
int n,k,p,i;int Pow(int x,int y)
{int s=1;for(;y;y>>=1,x=(ll)x*x%P)if(y&1)s=(ll)s*x%P;return s;
}int main()
{cin>>n>>k>>p;if(k==1)cout<<((ll)n*(n-1)/2%P*p+n)%P<<endl;else{i=Pow(k-1,P-2);cout<<((1+(ll)p*i)%P*(Pow(k,n)-1)%P*i-(ll)p*n%P*i%P+P)%P<<endl;}return 0;
}
转自:http://www.cnblogs.com/ALINGMAOMAO/p/9500268.html
ac:
#include<cstdio>
#include<cstring>
#define ll long long
#define mod int(1e9+7)
ll k, p;
struct jz
{ll num[3][3];jz(){ memset(num, 0, sizeof(num)); }jz operator*(const jz &p){jz ans;for (int k = 0; k < 3;++k)for (int i = 0; i < 3;++i)for (int j = 0; j < 3; ++j)ans.num[i][j] = (ans.num[i][j] + num[i][k] * p.num[k][j] % mod) % mod;return ans;}
}pp;
jz POW(jz x, ll n)
{jz ans;for (int i = 0; i < 3; i++) ans.num[i][j] = 1;for (; n; n>>=1, x=x*x)if (n & 1)ans = ans*x;return ans;
}
void init()
{pp.num[0][0] = 1; pp.num[0][1] = k; pp.num[0][2] = 1;pp.num[1][1] = k; pp.num[1][2] = 1; pp.num[2][2] = 1;
}
int main()
{ll n;scanf("%d%d%d", &n, &k, &p);ll s2 = 1 + k + p;if (n == 1){ printf("1\n"); return 0; }else if (n == 2){ printf("%lld\n", s2); return 0; }init();pp = POW(pp, n - 2);printf("%lld", (pp.num[0][0] + pp.num[0][1] + (p*pp.num[0][2])%mod) % mod);return 0;
}发电:
简单线段树,注意除法时需要用逆元处理
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#define lson l , m , rt << 1
#define rson m + 1 , r , rt << 1 | 1
#define maxn 1000007
#define mod 1000000007
#define ll long long
using namespace std;
int n,m,x,y,z;
long long sum[maxn];void pushup(int rt) {sum[rt] =(sum[rt<<1]*sum[rt<<1|1])%mod;
}ll finv2(ll a,ll b)
{ll res=1;b=b-2;while(b){if(b&1)res=res*a%mod;a=a*a%mod;b>>=1;}return res;
}void build(int l,int r,int rt){if (l == r) {sum[rt]=1;return ;}int m = (l + r) >> 1;build(lson);build(rson);pushup(rt);
}void update(int p,int add,int l,int r,int rt) {if (l == r) {sum[rt] =(sum[rt]*add)%mod;return ;}int m = (l + r) >> 1;if (p <= m) update(p , add , lson);else update(p , add , rson);pushup(rt);
}void update2(int p,int add,int l,int r,int rt) {if (l == r) {sum[rt] =sum[rt]*finv(add,mod)%mod;return ;}int m = (l + r) >> 1;if (p <= m) update2(p , add , lson);else update2(p , add , rson);pushup(rt);
}long long query(int L,int R,int l,int r,int rt) {if (L <= l && r <= R) {return sum[rt];}int m = (l + r) >> 1;long long a = 1,b=1;if (L <= m) a= query(L , R , lson);if (R > m) b= query(L , R , rson);return (a%mod*b%mod)%mod;
}int main()
{scanf("%d%d",&n,&m);build(1,n,1);for(int i=0;i<m;i++){scanf("%d%d%d",&x,&y,&z);if(x==1)update(y,z,1,n,1);else if(x==2)update2(y,z,1,n,1);elseprintf("%lld\n",query(y,z,1,n,1));}return 0;
}