友情提示：
这篇题解并没有GJKL，因为我也不会，而且看别人代码也看不懂，而且问学长还不给我讲！hmc：这个题巨麻烦，我只能说balabala。我不学了我退役了啊！
A：这傻逼题我从开头wa了四个小时然后我发现我写了各种奇葩东西，
嗯不说了。很明显要么在某线段起点开始要么在某线段终点结束。然后枚举段点二分就行。
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e5+;
struct Node{
ll l,r,v;
}node[N];
bool cmp(Node a,Node b){
return a.r<b.r;
}
ll t,m;ll k;
ll l[N],r[N],v[N],pre[N];
int main(){//什么东西啊这是
ios::sync_with_stdio(false);
cin>>t;
while (t--){
cin>>m>>k;
for(int i=;i<=m;i++){
cin>>node[i].l>>node[i].r>>node[i].v;
}
sort(node+,node++m,cmp);
for(int i=;i<=m;i++){
l[i]=node[i].l;
r[i]=node[i].r;
v[i]=node[i].v;
pre[i]=pre[i-]+(r[i]-l[i]+)*v[i];
}
l[m+]=2e9+;r[m+]=2e9+;
pre[m+]=pre[m]+;
ll ans = ;
for(int i=;i<=m;i++){
int id = lower_bound(r,r+m+,l[i]+k-)-r;//
ll tmp = pre[id-]-pre[i-];
if(l[i]+k->=l[id])
tmp+=(l[i]+k-l[id])*v[id];
ans = max(ans,tmp);
}
for(int i=;i<=m;i++){
int id = lower_bound(l,l+m+,r[i]-k+)-l;
ll tmp = pre[i]-pre[id-];
if(r[i]-k+<=r[id-]){
tmp+=(r[id-]-(r[i]-k+)+)*v[id-];
}
ans = max(ans,tmp);
}
cout<<ans<<endl;
}
}
/**
1
1 1000000000
2 1000000000 1000000000
*/
B：这。。。傻逼题吧。。。
#include <bits/stdc++.h>
#define mk(a,b) make_pair(a,b)
#define pii pair<int,int>
using namespace std;
typedef long long ll;
int t;
ll x,n;
ll ans[];
int main(){
ios::sync_with_stdio(false);
cin>>t;
while (t--){
memset(ans,, sizeof(ans));
cin>>x>>n;
if(n==){
cout<<x<<endl;
continue;
}
ll tmp = x/(*n-);
x%=*n-;
ans[]+=tmp;ans[n]+=tmp;
for(int i=;i<n;i++)
ans[i]+=tmp*;
for(int i=;i<=n;i++){
if(x<=) break;
ans[i]++;x--;
}
for(int i=n-;i>=;i--){
if(x<=) break;
ans[i]++,x--;
}
for(int i=;i<=n;i++){
cout<<ans[i]<<' ';
}
cout<<endl;
}
}
C：读错题wa自闭了。
#include <bits/stdc++.h>
#define mk(a,b) make_pair(a,b)
#define pii pair<int,int>
using namespace std;
typedef long long ll;
int main(){
ios::sync_with_stdio(false);
int t;ll n;
cin>>t;
while (t--){
cin>>n;
bool flag = false;
int ans = ;
for(int i=;i<=;i++){
if(!(n&(1ll<<i))){
ans++;
} else
break;
}
cout<<ans+<<endl;
}
}
D：别想什么横着竖着花里胡哨的，就一排一排的交错放就行。
#include <bits/stdc++.h>
#define mk(a,b) make_pair(a,b)
#define pii pair<int,int>
using namespace std;
typedef long long ll;
int t;
ll n,m;
int main(){
ios::sync_with_stdio(false);
cin>>t;
while (t--){
cin>>n>>m;
ll ans = 1e17;
if(n==){
cout<<(m+)/<<endl;
continue;
}
if(m==){
cout<<(n+)/<<endl;
continue;
}
if(n%==){
if(m%==){
ans = min(ans,n/*(m+));
ans = min(ans,m/*(n+));
} else{
ans = min(ans,n/*(m+));
ans = min(ans,m*n/+m/);
}
} else{
if(m%==){
ans = min(ans,m/*(n+));
ans = min(ans,n*m/+n/);
} else{
ans = min(ans,n*(m+)/);
ans = min(ans,m*(n+)/);
}
}
cout<<ans<<endl;
}
}
E：运用小学数学知识可以很轻松的发现这个递推式吧，写在代码里了。
#include <bits/stdc++.h>
#define mk(a,b) make_pair(a,b)
#define pii pair<int,int>
using namespace std;
typedef long long ll;
const ll mod = 1e9+;
const int N = 1E5+;
int t;
int n;
ll a[N];
ll pre[N];
ll f[N];
int main(){
ios::sync_with_stdio(false);
cin>>t;
while (t--){
cin>>n;
pre[]=1ll;
for(int i=;i<=n;i++) {
cin >> a[i];
pre[i] = pre[i - ] * a[i] % mod;
}
f[]=a[]-;
for(int i=;i<=n;i++){
f[i]=(a[i]*f[i-]+pre[i-]*(a[i]-))%mod;
}
cout<<f[n]<<endl;
}
}
F：我很知趣的没用memset，被这个东西坑死太多次了，然后枚举每个ai就完了
#include <bits/stdc++.h>
#define mk(a,b) make_pair(a,b)
#define pii pair<int,int>
using namespace std;
typedef long long ll;
const int N = 1e5+;
int t,n,a[N];
int vis[*N];
int qaq(int x){
int tmp = x;
for(int i=;i*i<=x;i++){
if(x%i==){
if(vis[i]) {
tmp = min(tmp, i);
break;
}
if(vis[x/i]) {
tmp = min(tmp, x/i);
}
}
}
return tmp;
}
vector<int> v;//***
int main(){
ios::sync_with_stdio(false);
cin>>t;
while (t--){
cin>>n;
for(int i=;i<=n;i++){
cin>>a[i];
vis[a[i]]=;
v.push_back(a[i]);
}
ll sum = ;
for(int i=;i<=n;i++){
a[i] = qaq(a[i]);
sum+=a[i];
}
for(auto a:v){
vis[a]=;
}
v.clear();
cout<<sum<<endl;
}
}
H：。。。
#include <bits/stdc++.h>
#define mk(a,b) make_pair(a,b)
#define pii pair<int,int>
using namespace std;
typedef long long ll;
int main(){
ios::sync_with_stdio(false);
int t,n,a[];
cin>>t;
while (t--){
cin>>n;
for(int i=;i<=*n;i++)
cin>>a[i];
int maxx = ;
for(int i=;i<=*n;i++){
maxx = max(maxx,a[i]+a[*n-i+]);
}
cout<<maxx<<endl;
}
}
I：。。。
#include <bits/stdc++.h>
#define mk(a,b) make_pair(a,b)
#define pii pair<int,int>
using namespace std;
typedef long long ll;
int t,x,n;
int main(){
ios::sync_with_stdio(false);
cin>>t;
while (t--){
cin>>x>>n;
int tmp = x/n;
if(tmp==){
cout<<-<<endl;
continue;
}
if(x%n==){
for(int i=;i<=n;i++)cout<<tmp<<' ';
} else{
vector<int> ans;
for(int i=;i<=x%n;i++)
ans.push_back(tmp+);
for(int i=x%n;i<n;i++)
ans.push_back(tmp);
reverse(ans.begin(),ans.end());
for(auto a: ans) cout<<a<<' ';
}
cout<<endl;
}
}
M：lca板子题，用的cincout然后tle三发自闭了。快读大法好
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e5+;
inline int read() {
int X=,w=; char c=getchar();
while (c<''||c>'') { if (c=='-') w=-; c=getchar(); }
while (c>=''&&c<='') X=(X<<)+(X<<)+c-'',c=getchar();
return X*w;
}
struct Node{
int to,v1,v2;
};
vector<Node>g[N];
int s1[N],s2[N];
int t,n,q;
int par[N][],dep[N],deg[N];
void dfs(int v,int fa){
dep[v]=dep[fa]+;
par[v][]=fa;
for(int i=;(<<i)<=dep[fa];i++)
par[v][i]=par[par[v][i-]][i-];
for(int i=;i<g[v].size();i++){
int u = g[v][i].to;
if(u==fa)
continue;
s1[u]=s1[v]+g[v][i].v1;//下来
s2[u]=s2[v]+g[v][i].v2;//上去
//down[v]+=g[v][i].v1+g[v][i].v2;
dfs(u,v);
//down[v]+=down[u];
}
}
int lca(int x,int y){
if(dep[x]>dep[y])
swap(x,y);
for(int i=;i>=;i--)
if(dep[x]<=dep[y]-(<<i))
y = par[y][i];
if(x==y)
return x;
for(int i=;i>=;i--) {
if (par[x][i] == par[y][i])
continue;
else
x=par[x][i],y=par[y][i];
}
return par[x][];
}
void init(){
for(int i=;i<=1e5;i++)
g[i].clear();
memset(par,, sizeof(par));
memset(dep,, sizeof(dep));
memset(deg,, sizeof(deg));
memset(s1,, sizeof(s1));
memset(s2,, sizeof(s2));
}
int main(){
t = read();
while (t--){
init();
cin>>n;
int u,v,c1,c2;
int all = ;
for(int i=;i<n;i++){
u=read();v=read();c1=read();c2=read();
deg[u]++;
deg[v]++;
all+=c1+c2;
g[u].push_back(Node{v,c1,c2});
g[v].push_back(Node{u,c2,c1});
}
for(int i=;i<=n;i++){
if(deg[i]==){
dfs(i,);
break;
}
}
q=read();
while (q--){
u=read();v=read();
int baba = lca(u,v);
int ans = all;
ans -= s2[v]-s2[baba];
ans -= s1[u]-s1[baba];
printf("%d\n",ans);
}
}
}