行走天涯的豆沙包-CSDN博客

原创 GAT源码剖析

题解：首先挂出核心公式和训练过程生成的aij注意系数layer.pyimport numpy as npimport torchimport torch.nn as nnimport torch.nn.functional as Fclass GraphAttentionLayer(nn.Module): """ Simple GAT layer, similar to https://arxiv.org/abs/1710.10903 """ def __

2021-01-06 17:29:44 1887 3

原创 GCN——源码剖析

图学习layer.pyimport mathimport torchfrom torch.nn.parameter import Parameter # 可以用parameter()函数from torch.nn.modules.module import Module # 定义网络层的模块'''parameter()将一个不可训练的类型Tensor转换成可以训练的类型parameter并将其绑定到这个module里面，所以经过类型转换这个就变成了模型的一部分，成为了模型

2021-01-05 17:23:34 1195 2

原创 Joty and Chocolate

题解：容斥定理。#include<bits/stdc++.h>#define int long longusing namespace std;int lcm(int a,int b){ return a*b/__gcd(a,b);}void solve(){ int n,a,b,p,q; cin>>n>>a>>b>>p>>q; cout<<n/a*p+n/b*q-min(p,q)*

2020-12-22 21:53:43 185

原创 Number With The Given Amount Of Divisors

题解：反素数。直接套板子就好了。#include<bits/stdc++.h>#define int unsigned long longusing namespace std;const int inf=~0ULL;int p[16] = {2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53};int res,n;void dfs(int dep,int tmp,int num){ if(num>n) return ;

2020-12-22 21:13:19 110

原创 Coprime Triples——CodeChef - COPRIME3

题解：对数等于u(x)∗C(D(x),3)u(x)*C(D(x),3)u(x)∗C(D(x),3)#include <bits/stdc++.h>using namespace std;#define maxn 1000000 + 5int n, maxai, i, ai, a[maxn], p[maxn], dp[maxn], j;long long ret, kol;bool vis[maxn];int prime[maxn],mu[maxn];void init_mu(i

2020-12-22 11:32:06 198

原创 2020 CCPC Wannafly Winter Camp Day7 G

草莓2如果k<mn那么暴搜一下就行了，如果大于。那么我们走完每一个地方后，我们每次走都是一个环并且走k−m∗nk-m*nk−m∗n次。每次权值是mn。#include<bits/stdc++.h>using namespace std;#define ll long longint a[12][12],t[12][12];int to[4][2] = {{1, 0}, {-1, 0}, {0, -1}, {0, 1}};ll k, n, m;ll ans = 0;void

2020-12-02 22:30:17 220

原创 BF的数据结构题单-提高组——P2680 运输计划

题解：题目让我们找一条边变成0，然后让整个运输航线的距离总和最短。也就是最大的最短，所以可以用二分。然后我们可以知道这个边一定在最长的那条链上面所以在树上差分找到经过次数最多的那条链。#include <bits/stdc++.h>using namespace std;typedef long long ll;inline int read(){ int p=0,f=1;char c=getchar(); while(c<'0'||c>'9'){if(c

2020-11-15 16:35:03 170

原创 BF的数据结构题单-提高组——P2590 [ZJOI2008]树的统计

没啥好说的，还是板题。#include<bits/stdc++.h>using namespace std;#define ls rt<<1#define rs rt<<1|1const int N=3e4+10;int head[N],e[N<<1],nw[N],ne[N<<1],w[N],cnt,n;struct Segment_Tree{ static const int maxn = 1e5 + 5; stru

2020-11-14 16:21:15 151

原创 BF的数据结构题单-提高组——树链剖分

树链剖分板子题#include <bits/stdc++.h>using namespace std;#define ll long long#define ls 2 * rt#define rs 2 * rt + 1#define N 100005int n, m; vector<int> edge[N];int id[N], nw[N], w[N], tot;int dep[N], sz[N], top[N], fa[N], son[N],r,mod;inli

2020-11-14 00:52:38 794

原创 BF的数据结构题单-提高组——P1783 海滩防御

题解：二分+并查集超时了，然后想了下可以用生成树来做，答案一定是每个点的左右距离和两两距离和之内产生。#include<bits/stdc++.h>using namespace std;const int N=1e5+10;const double esp=1e-3;int n,m,pre[N];typedef pair<int, int> pp;map<pp,int> mp;vector<pp> g;struct Node{

2020-11-12 12:36:10 187

原创 BF的数据结构题单-提高组 ——P1197 [JSOI2008]星球大战

P1197 [JSOI2008]星球大战题解：经典题，反向加边。#include<bits/stdc++.h>using namespace std;const int N=4e5+10;vector<int> g[N];int pre[N];typedef pair<int,int> pp;vector<pp> edge;int res[N],cnt,vis[N],a[N];int find(int a){ if(pre[a]

2020-11-11 23:48:53 184

原创 G. Reducing Delivery Cost

题解：题意让我们让一条边变成0，然后计算k条路的路径总和最小是多少。我们选择的边有两种情况，分别是选的时候这条边是否在最短路上面，所以我们预处理出所有点与点之间的最短距离，然后枚举让哪条边的权值变成0。#include<bits/stdc++.h>//#define int long longusing namespace std;const int N=1e3+10;typedef pair<int,int> pp;int head[N],e[N<<1],

2020-10-29 10:53:22 302

原创 D. Shurikens

题解：我们逆向思考，如果我们反着拿的过程中，我们没次连续拿出来的货物的价格一定是递减的。所以就是一个栈的模拟过程。#include<bits/stdc++.h>//#define int long longusing namespace std;const int N=3e4+10;typedef pair<int,int> pp;vector<pp> g;void solve(){ int n; cin>>n; for(in

2020-10-28 20:41:19 366

原创 CCPC威海站

这场整场都很迷，先是A题贡献6发罚时，然后L题读错题近1个小时。如果L题能读对的话说不定能节约很多时间想出分组背包，那么就可以解决时间给ar去过C题，说不定可以6题可以银的硬生生变成了铜尾。L题解：我们需要让分解出来的lcm最大那么就是一些互质的数或者是他们的次数幂，所以每一个幂次可以看成一组背包，那么我们就可以用分组背包。因为相同底数多选的话lcm就是计算最高的那个幂次，所以就是选不选，选的话就只选一组中的一个的分组背包问题。需要预处理log不然回T。#include<bits/stdc++.

2020-10-27 10:48:10 552

原创期望DP——珂学送分

题解：dp[i]dp[i]dp[i]代表[i…n]这个区间分成多少段的期望值我们从后面往前面扫描，当我们发现i−ji-ji−j这个范围是满足的话，那么我们可以切分的点就存在j−i+1j-i+1j−i+1个点。假设我们选择点k，k属于[i,j][i,j][i,j]这个区间，那么我们这段的期望就是1/len1/len1/len乘以(dp[k+1]+1)，k属于[i,j][i,j][i,j]。#include<bits/stdc++.h>//#define int long longusin

2020-10-27 00:20:09 177

原创 E. Two Round Dances

先贴代码题解明天写#include<bits/stdc++.h>#define int long longusing namespace std;signed main(){ cin.tie(0);std::ios::sync_with_stdio(false); int n;cin>>n; int fac=1; for(int i=1;i<=n;i++){ fac=fac*i; } fac*=2;

2020-10-21 22:59:31 197 1

原创矩阵乘法——OpenJ_POJ - C16H

题解：首先知道我们每一个球的扩散是只向四个方向扩散，所以我们新产生的贡献分成了两部分，一部分是复制一份移动四个方向，然后移动的时候在新的位置上加上坐标的净增长值就是这一次的坐标总和了。#include<bits/stdc++.h>#define int long longusing namespace std;const int N=2e4+10;int a[N],b[N];const int mod=1e9+7;struct Matrix{ long long a[2

2020-10-09 16:11:22 190

原创构造——ZOJ - 4033

题解：找出无解的情况之后，4个或者3个分成一组就可以了。#include <bits/stdc++.h>using namespace std;const int N=1e6+10;char a[N];int res[N];void solve(){ int n; scanf("%d",&n); scanf("%s",a+1); if(n%4!=0&&n%4!=3){ puts("-1"); retu

2020-10-06 20:03:58 193

原创数位dp——Great Deceiver

题解：下标为奇数位置上的数的系数必须要为0剩下的就是数位dp了。#include <bits/stdc++.h>#define int long longusing namespace std;const int N=100;int n,m,k;int a[N],f[N];int dfs(int idx,int limit){ if(idx==0) return 1; if(!limit&&f[idx]!=-1) return f[idx];

2020-10-06 12:30:54 1849

原创概率dp——跑路ing

题解：既然等概率又收敛，多跑一百次就是答案了。#include <bits/stdc++.h>using namespace std;int n,m,k;const int N=100+10;double f[N][N];vector<int> g[N];void solve() { int n,m; while(~scanf("%d%d",&n,&m)) { for (int i = 1; i <= n; i++

2020-10-05 21:43:06 184

原创期望DP——配对游戏

题解：f(i,j)f(i,j)f(i,j)定义为前i个人，被抵消掉过后还剩j个人向右看。求出来过后的期望乘以2就行了。#include <bits/stdc++.h>using namespace std;int n,m,k;const int N=1e5+10;int dp[2010][2010];void solve(){ memset(dp,0,sizeof(dp)); int n; scanf("%d", &n); dp[0][0]

2020-10-05 18:30:33 164

原创期望DP——景区路线规划

题解：分开算男女的期望，因为是等概率出现各个景点，并且是等概率选择分支景点，所以记忆化搜索满意度和再除以n就行了。#include <bits/stdc++.h>using namespace std;int n,m,k;const int N=1e5+10;int ci[N],h[N][3];double f[105][500][3];typedef pair<int,int> pp;vector<pp> g[N];double dfs(int u,

2020-10-05 14:47:14 232

原创概率DP——比赛

题解：我们知道一个题做不出的概率，用1减去就是能做的概率，然后直接概率dp就行了。f(i,j)f(i,j)f(i,j)代表前i个题能做出j个题的概率。#include <bits/stdc++.h>//#define int long longusing namespace std;const int N=1e6+10;double a[N],b[N],c[N],d[N];double f[100][100];void solve(){ for(int i=1;i&lt

2020-10-03 13:30:21 141

原创树

题解：我们把树切割成多个连通块，每个连通块的颜色不同，分成多个连通块的方法就是切边。#include <bits/stdc++.h>#define int long longusing namespace std;typedef long long ll;const int mod=1e9+7;const int N=1e5+10;vector<int> g[N];int fac[N],inv[N];int qmi(int a,int b){ int r

2020-09-29 15:38:04 161

原创 Paint Box

题解：我们知道至少涂k种颜色并且相邻两个不相邻的方案数为:k(k−1)n−1k(k-1)^{n-1}k(k−1)n−1。然后容斥一下就可以了。#include<bits/stdc++.h>using namespace std;#define ll long longconst ll mod=1e9+7;const int maxn=1e6+10;int T;ll p[maxn], invp[maxn], inv[maxn];ll qp(ll a, ll b){ a %

2020-09-29 10:04:56 371

原创 ac自动机——[TJOI2013]单词

题解：建fail树之后，从下往上跑fail指针并且计数。答案就是每个节点的计数。#include <bits/stdc++.h>//#define int long longusing namespace std;typedef long long ll;const int N=1e6+10;const int M=1e5+10;const int mod=1e9+7;vector<int> g;vector<int> id;int head[N],

2020-09-28 16:26:02 78

原创 AC自动机——[HEOI2012]旅行问题

题解：明天补，吃了感冒药。#include <bits/stdc++.h>//#define int long longusing namespace std;typedef long long ll;const int N=1e6+10;const int M=1e5+10;const int mod=1e9+7;vector<int> g[M];int head[N],e[N],ne[N],idx;void add(int a,int b){ e[

2020-09-27 22:08:57 172 1

原创 E - Sequence in the Pocket

题解：我们直接排序，然后就可以知道最后结果是如何得。我们要保证操作得数最小，所以要保证更多得数在原位上面数更多的保持不变。所以扫一遍找出需要移动的位置。#include <bits/stdc++.h>//#define int long longusing namespace std;typedef long long ll;const int N=1e5+10;int a[N],b[N];void solve(){ int n; scanf("%d",&n);

2020-09-24 18:35:33 170

原创 2020.9.22训练

[Contest #16]小 C 的数论习题CRT板子题，但是题目中要求输出的是整数，所以res=0的时候我们输出232332333。#include <bits/stdc++.h>//#define int long longusing namespace std;const int N=1e5+10;int a[10],m[10],n=3;typedef long long ll;ll exgcd(ll a,ll b,ll &x,ll &y){ if

2020-09-22 10:30:28 91

原创 2020-9-21训练

B. Balls of Buma祖玛游戏，如果我们只射出一个子弹可以把所有都消掉的话那么我们分段的数量一定是一个奇数，然后对称的地方的种类是相同的并且对称位置相加后的数字一定是大于3的。#include <bits/stdc++.h>//#define int long longusing namespace std;const int N=3e5+10;int a[N],pos[N];char s[N];void solve(){ cin>>s+1;

2020-09-21 19:40:01 360

原创树套树——线段树套set

请你写出一种数据结构，来维护一个长度为 n 的序列，其中需要提供以下操作：1 pos x，将 pos 位置的数修改为 x。2 l r x，查询整数 x 在区间 [l,r] 内的前驱(前驱定义为小于 x，且最大的数)。数列中的位置从左到右依次标号为 1∼n。区间 [l,r] 表示从位置 l 到位置 r 之间（包括两端点）的所有数字。区间内排名为 k 的值指区间内从小到大排在第 k 位的数值。（位次从 1 开始）输入格式第一行包含两个整数 n,m，表示数列长度以及操作次数。第二行包含 n 个整数

2020-09-19 22:44:34 315

原创 C. Square Subsets

题解：题目让找几个数的乘积是一个完全平方数，我们知道完全平方数的质因数分解之后的因子的指数都是偶数，70以内的素数只有10多个，所以选择用状压dp。我们状压的状态就是这些素数因子的指数是否为偶数。选择一个数的时候相当于把这个数的连续质因子指数加到另一个质因子的指数上面，当我们这个质因子的指数为偶数的时候那么加上偶数不影响当前的奇偶性，直接由上一个状态转移过来就行了。为奇数的时候就转移到亦或为0的状态。根据二项式定理我们知道，k个数里选1，3，5。。这样的奇数个的方案为2k−12^{k-1}2k−1，偶数的

2020-09-18 19:56:10 124

空空如也

空空如也