day1
t1
转圈游戏（circle）
裸地快速幂。。
#include<cstdio>
using namespace std;
int n,m,x,k;
int fastpow(int a,int k){int ans=1;while(k){if(k&1) ans=(1ll*ans*a)%n;a=(1ll*a*a)%n;k>>=1;}return ans;
}
int main() {scanf("%d%d%d%d",&n,&m,&k,&x);printf("%d",(x+1ll*m*fastpow(10,k)%n)%n);return 0;
}t2
火柴排队
这个题可以贪心，最小价值一定是大小位置对应的，所以用下面的匹配上面的就行了
因为火柴棒数目有点大，需要离散化一下，因为火柴的长度不一。
然后可以对第一个串遍一个号，对应到第二个串里，就变成了两两交换排序问题
再一次转换为逆序对问题，就a了
#include<cstdio>
#include<algorithm>
using namespace std;
#define ll long long
const int M=101001;
const int P=99999997;
struct st{ll f,s;};
int n;
st a[M];ll t[M],w[M],sum[M],ans,ff[M],tmp[M],tmp2[M];
void add(ll x){for(;x;x-=x&(-x)) sum[x]++;
}
ll ask(ll x){ll tot=0;for(;x<=n;x+=x&(-x))tot=(tot+sum[x])%P;return tot;
}
int main(){scanf("%d",&n);for(int i=1;i<=n;i++) scanf("%lld",&a[i].f),t[i]=a[i].f;for(int i=1;i<=n;i++) scanf("%lld",&a[i].s),w[i]=a[i].s;sort(t+1,t+n+1);sort(w+1,w+n+1);for(int i=1;i<=n;i++){a[i].f=lower_bound(t+1,t+n+1,a[i].f)-t;a[i].s=lower_bound(w+1,w+n+1,a[i].s)-w;}for(int i=1;i<=n;i++) ff[a[i].f]=i;for(int i=1;i<=n;i++){add(ff[a[i].s]);ans=(ans+ask(ff[a[i].s]+1))%P;}printf("%lld",ans%P);return 0;
}t3
货车运输
先找出最大生成森林，再找倍增找lca，找最小值
之前写了个tarjan错了。。。
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
#define ll long long
const int M=21000,INF=1e9+3;
int fa[M],vis[M],tote,heade[M],nexe[M*2],toe[M*2],cose[M*2],tot,head[M],nex[M*2],to[M*2],cos[M*2],f[M],dep[M];
int ff[M],zx[M],cnt,dx[M],dy[M],up[M][20],g[M][20];
int n,m,q;
struct st{int x,y,z;
}a[M];
bool cmp(const st a,const st b){return a.z>b.z;
}
void add(int x,int y,int z){nex[++tot]=head[x];to[tot]=y;cos[tot]=z;head[x]=tot;
}
void adde(int x,int y){nexe[++tote]=heade[x];toe[tote]=y;heade[x]=tote;
}
int find(int x){return f[x]==x?x:f[x]=find(f[x]);
}void K(){int j=1,num=n;while(j<=m){int fx=find(a[j].x);int fy=find(a[j].y);if(fx==fy) {j++;continue;}f[fx]=fy;add(a[j].x,a[j].y,a[j].z);add(a[j].y,a[j].x,a[j].z);j++;num--;if(num==1) break;}}
void dfs(int x){vis[x]=1;for(int i=head[x];i;i=nex[i]){int tmp=to[i];if(!vis[tmp]){up[tmp][0]=x;g[tmp][0]=cos[i];dep[tmp]=dep[x]+1; dfs(tmp); }}}
int lca(int x,int y)
{ if(x==y) return 0;int fx=find(x);int fy=find(y);if(fx!=fy) return -1;int minx=INF,miny=INF;if(dep[x]<dep[y]) swap(x,y);for(int i=18;i>=0;i--){if(dep[up[x][i]]>=dep[y]&&up[x][i]){minx=min(minx,g[x][i]);x=up[x][i];}}if(x==y) return minx;for(int i=18;i>=0;i--){if(up[x][i]!=up[y][i]){minx=min(minx,g[x][i]);miny=min(miny,g[y][i]);x=up[x][i];y=up[y][i];}}minx=min(minx,g[x][0]);miny=min(miny,g[y][0]);return min(minx,miny);
}
int main(){scanf("%d%d",&n,&m);for(int i=1;i<=m;i++)scanf("%d%d%d",&a[i].x,&a[i].y,&a[i].z);for(int i=1;i<=n;i++)f[i]=i;sort(a+1,a+m+1,cmp);K();memset(g,127,sizeof g);scanf("%d",&q);for(int i=1;i<=q;i++){scanf("%d%d",&dx[i],&dy[i]);adde(dx[i],dy[i]);adde(dy[i],dx[i]);}for(int i=1;i<=n;i++) if(!vis[i])dfs(i);for(int j=1;(1<<j)<=n;j++) for(int i=1;i<=n;i++)if(up[up[i][j-1]][j-1]!=0){up[i][j]=up[up[i][j-1]][j-1];g[i][j]=min(g[i][j-1],g[up[i][j-1]][j-1]);}//for(int i=1;i<=2*q;i++) printf("%d ",lca[i]);for(int i=1;i<=q;i++){if(find(dx[i])!=find(dy[i])) printf("-1\n");elseprintf("%d\n",lca(dx[i],dy[i]));}
} day2
t1
这个题正解是单调栈，因为山包你把它砍掉就行，只有上升可以增加高度，下降就可以直接去掉
这就是个单调栈，然后更新答案，用山顶减山脚
我是用了个优先队列+链表，也搞对了，我是每一次砍掉最高的山，然后把最高的山去掉，你可以看做和旁边的山合并成一个山了，这个可以用优先队列，然后记录个左右山的序号，用看得比较小的，更新答案，删山时用链表搞一下
#include<cstdio>
#include<iostream>
#include<queue>
using namespace std;
const int M=110000;
struct st{int x,t;inline int operator <(const st &a)const{return a.x<x;}};
int n,a[M];
int cnt=1,f=1,h[M],minn[M];int ans,l[M],r[M];
priority_queue < st > q;
int t=0;
int main(){scanf("%d",&n);for(int i=1;i<=n;i++){scanf("%d",&a[i]);if(a[t]!=a[i]){st tmp;tmp.x=-a[i];tmp.t=i;q.push(tmp);l[i]=t,r[t]=i;t=i;}}while(!q.empty()){st tmp=q.top();//printf("%d ",-tmp.x);q.pop();l[r[tmp.t]]=l[tmp.t];r[l[tmp.t]]=r[tmp.t];ans+=min(-tmp.x-a[l[tmp.t]],-tmp.x-a[r[tmp.t]]);}printf("%d",ans);
}t2
花匠
想一个问题，最后选的花一定是波浪线，一定包括所有峰（比左右都大得），所以结果就是峰的个数乘2
在特判一下两端是否是峰
#include<cstdio>
#include<iostream>
using namespace std;
int n,a[1999999],tot;
int s,f;
int main(){scanf("%d",&n);for(int i=1;i<=n;i++) {int x;scanf("%d",&x);if(a[tot]!=x) a[++tot]=x;}for(int i=1;i<=tot;i++) {if(a[i]>a[i-1]&&a[i]>a[i+1]) s++;}s=s*2;if(a[1]<a[2]) s++;if(a[tot]>a[tot-1]) s--;printf("%d",s);
}t3
华容道