题解:
喵哈哈村的魔力源泉(1)
题解:签到题。
代码:
#includeusing namespace std;int main(){ long long a,b,c; while(cin>>a>>b>>c){ cout< <
喵哈哈村的魔力源泉(2)
题解:首先快速幂是来处理次方的问题,那么我们模仿快速幂,写一个快速加即可,这样我们每次乘以2,就不会爆longlong了
代码:
#include#include #include #include #include #include #include #include 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< <
喵哈哈村的魔法源泉(3)
题解:答案实际上就是树的直径的一半,关于树的直径,这个自己百度吧~
代码:
#include#include #include #include #include #include #include using namespace std;const int maxn=200050;vector son[maxn],w[maxn];bool vis[maxn];int f[maxn];int bfs(int root){int i,j,k;int ans=root,maxx=0;queue 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
喵哈哈村的魔力源泉(4)
题解:单调队列优化的dp,这儿有个链接比我讲得清楚。。。
代码:
#include#include 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<
喵哈哈村的魔力源泉(5)
题解:类似two pointer去做,维护最小边,然后去枚举最大边。用带权并查集去维护每个集合的边的信息,如果所有点都大于等于了k,那么就输出答案即可。
代码:
#include#include #include #include #include #include #include #include #include