喵哈哈村的魔法考试 Round #19 (Div.2) 题解

题解:

喵哈哈村的魔力源泉(1)

题解:签到题。

代码:

#include<bits/stdc++.h>
using namespace std; int main(){
long long a,b,c;
while(cin>>a>>b>>c){
cout<<a*b%c<<endl;
}
}

喵哈哈村的魔力源泉(2)

题解:首先快速幂是来处理次方的问题,那么我们模仿快速幂,写一个快速加即可,这样我们每次乘以2,就不会爆longlong了

代码:

#include <iostream>
#include <cstdlib>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <queue>
#include <vector> using namespace std;
long long a,b,p;
long long ksj(long long a,long long b)
{
if(b==0)return 0;
if(b==1)return a%p;
long long sb=ksj(a,b/2);
sb=(sb+sb)%p;
if(b&1)
return (sb+a)%p;
else
return sb;
}
void read_in()
{
while(scanf("%lld%lld%lld",&a,&b,&p)!=EOF){
cout<<ksj(a,b)<<endl;
}
}
int main()
{
read_in();
return 0;
}

喵哈哈村的魔法源泉(3)

题解:答案实际上就是树的直径的一半,关于树的直径,这个自己百度吧~

代码:

#include<iostream>
#include<cstdio>
#include<vector>
#include<queue>
#include<cmath>
#include<algorithm>
#include<cstring>
using namespace std;
const int maxn=200050;
vector<int> son[maxn],w[maxn];
bool vis[maxn];
int f[maxn];
int bfs(int root)
{
int i,j,k;
int ans=root,maxx=0;
queue<int> q;
memset(vis,0,sizeof(vis));
memset(f,0,sizeof(f));
q.push(root);
vis[root]=1;f[root]=0;
while(!q.empty())
{
root=q.front();
q.pop();
for(i=0;i<son[root].size();i++)//À©Õ¹Â·¾¶
{
if(vis[son[root][i]]==0)//È¥ÖØ
{
q.push(son[root][i]);
vis[son[root][i]]=1;
f[son[root][i]]=f[root]+w[root][i];
if(maxx<f[son[root][i]])
{
maxx=f[son[root][i]];
ans=son[root][i];//ansÊÇÄ¿Ç°¾àÀëROOT×îÔ¶µÄ½Úµã¡£
}
}
}
}
return ans;
}
int solve(int root)
{
int u,v;
u=bfs(root);
v=bfs(u);
return f[v];
} int main()
{
int i,j,k,n,m;
int x1,x2,l,u;
scanf("%d",&n);
for(i=0;i<n;i++)
{
son[i].clear();
w[i].clear();
}
for(i=0;i<n-1;i++)
{
scanf("%d%d%d",&x1,&x2,&l);
son[x1].push_back(x2);w[x1].push_back(l);
son[x2].push_back(x1);w[x2].push_back(l);
}
double ans=solve(1)/2.0;
printf("%0.1f\n",ans);
return 0;
}

喵哈哈村的魔力源泉(4)

题解:单调队列优化的dp,这儿有个链接比我讲得清楚。。。

http://blog.csdn.net/oiljt12138/article/details/51174560

代码:

#include<iostream>
#include<cstdio>
using namespace std;
struct node
{
long long s;
int n;
}q[1000010];
int a,n,m;
long long s[1000010],ans;
int h,t;
int main()
{
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++)
{
scanf("%d",&a);
s[i]=a+s[i-1];
}
q[0].s=0;q[0].n=0;
for(int i=1;i<=n;i++)
{
long long r=s[i];
r-=q[t].s;
ans=max(ans,r);
while(t<=h&&q[h].s>s[i])h--;
q[++h].s=s[i];
q[h].n=i;
while(q[t].n<=i-m)t++;
}
cout<<ans;
return 0;
}

喵哈哈村的魔力源泉(5)

题解:类似two pointer去做,维护最小边,然后去枚举最大边。用带权并查集去维护每个集合的边的信息,如果所有点都大于等于了k,那么就输出答案即可。

代码:

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <algorithm>
#include <string>
#include <cstring>
#include <vector>
#include <map> #define maxlongint 2147483647
#define pb push_back
#define mp make_pair
#define LL long long using namespace std; struct dwell
{
int a,b;
LL w;
} key[5010]; struct bz
{
int where,cnt;
} fa[1010]; LL like[1010];
LL k;
int n,m; bool cmp(dwell A,dwell B)
{
return A.w<B.w;
} int Findset(int x)
{
if(fa[x].where==x)return x;else return Findset(fa[x].where);
} int main()
{
scanf("%d%d%d",&n,&m,&k);
for(int i=1;i<=n;i++)scanf("%I64d",&like[i]);
for(int i=1;i<=m;i++)
scanf("%d%d%I64d",&key[i].a,&key[i].b,&key[i].w);
sort(key+1,key+m+1,cmp);
key[0].a=0;key[0].b=0;key[0].w=-100000000;
key[m+1].a=0;key[m+1].b=0;key[m+1].w=-100000000;
LL Minhz=-1,Maxhz=key[m].w+1,ans=0;
for(int i=1;i<=m;i++)
if(key[i].w!=key[i-1].w)
{
for(int j=1;j<=n;j++)
{
fa[j].where=j;
fa[j].cnt=1;
}
int j=i;
LL ans0=like[1]*n;
while(j<=m)
{
if(key[j].w-key[i].w>=Maxhz-Minhz)break;
int j0=j;
while(key[j0].w==key[j].w)j0++;
for(int x=j;x<j0;x++)
{
int s1=Findset(key[x].a),s2=Findset(key[x].b);
if(s1!=s2)
{
int X0=fa[s1].cnt,Y0=fa[s2].cnt;
ans0+=(like[X0+Y0]-like[X0]-like[Y0]);
fa[s1].cnt=X0+Y0;
fa[s2].cnt=X0+Y0;
if(s1>s2)fa[s1].where=s2;else fa[s2].where=s1;
if((ans0>=k)&&((Maxhz-Minhz>key[j].w-key[i].w)||(ans<k)))
{
ans=ans0;
Maxhz=key[j].w;
Minhz=key[i].w;
}
}
}
j=j0;
}
}
if(ans>=k)
printf("%lld\n",Maxhz-Minhz);
else
printf("T_T\n");
// system("pause");
return 0;
}
上一篇:喵哈哈村的魔法考试 Round #1 (Div.2) 题解&源码(A.水+暴力,B.dp+栈)


下一篇:Linux添加目录到环境变量以及添加sublime到环境变量