拖了一周才完成的题解，抛出一个可爱的表情 (っ'-')╮ =͟͟͞͞❤️。对我来说E、F比较难，都是线段树的题，有点久没写了。
A - Infinite Sequence
公差为c，首项为a的等差数列是否有一项等于b。
注意c为0的情况。
#include<cstdio>
long long a,b,c;
int main() {
scanf("%lld%lld%lld",&a,&b,&c);
if(c==0&&b==a||c&&(b-a)%c==0&&(b-a)/c>=0)puts("YES");
else puts("NO");
return 0;
}
B - Modular Inverse
求逆元。以前写过题解，http://www.cnblogs.com/flipped/p/5193777.html
C - * rearrangement
两个*各有m个犯人，现在各拿出相同个犯人交换，给定两个*有那些犯人是不能在一个*的，求最多交换多少人，且不超过m/2。
先用dfs计算出二分图的联通子图的左边的个数和右边的个数，然后用动态规划：
\(dp[i][j]\)表示左边共选了i个人，右边j个人交换是否可行。
\(dp[i][j]|=dp[i-le[i]][j-re[i]]\)
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<cmath>
#define ll long long
#define N 305
using namespace std;
int s,m,r,g[N][N];
int cnt,le[N],re[N];
int dp[N][N];
bool vis[2][N];
void dfs(int v,int c){
vis[c][v]=1;
if(c)le[cnt]++;else re[cnt]++;//连通图左边、右边的点个数
for(int i=1;i<=m;i++)//c==1，左边走到右边
if((c&&g[v][i]||!c&&g[i][v])&&!vis[!c][i]) dfs(i,!c);
}
int main() {
scanf("%d",&s);
for(int cas=1;cas<=s;cas++){
for(int i=0;i<N;i++)le[i]=re[i]=vis[0][i]=vis[1][i]=0;
memset(g,0,sizeof g);
memset(dp,0,sizeof dp);
cnt=0;
scanf("%d%d",&m,&r);
for(int i=1;i<=r;i++){
int x,y;
scanf("%d%d",&x,&y);
g[x][y]=1;
}
for(int i=1;i<=m;i++)
for(int c=0;c<2;c++)
if(!vis[c][i]){
cnt++;
dfs(i,c);
}
dp[0][0]=1;
for(int i=1;i<=cnt;i++)
for(int j=m/2;j>=le[i];j--)
for(int k=m/2;k>=re[i];k--)
dp[j][k]|=dp[j-le[i]][k-re[i]];
int i=m/2;
while(i&&dp[i][i]==0)i--;
printf("%d\n",i);
}
return 0;
}
D - Task Schedule
n个任务，m个机器，每台机器每天只能做一个任务，每个任务允许时间范围\([s_i,e_i]\)，需要时间长度\(p_i\)。求能否安排所有任务使得它们都能完成。
网络流最大流：
构图：1. 源点s->任务，容量p。2. 日子->汇点t，容量m。3. 任务->允许范围的日子，容量1。
用isap可以直接过，dinic我超时了，当前弧优化后就过了。
优化后的dinic：
#include <cstdio>
#include <cstring>
#include <queue>
#include <algorithm>
using namespace std;
#define N 1005
#define M 2000005
#define INF 0x7fffffff
struct edge{
int to,next,w;
}e[M];
int head[N],g[N],cnt;
int d[N],ans,tans;
int st,ed;
void add(int u,int v,int w){
e[cnt]=(edge){v,head[u],w};head[u]=cnt++;
e[cnt]=(edge){u,head[v],0};head[v]=cnt++;//反向弧
}
int bfs(){
memset(d,-1,sizeof d);
queue<int>q;
q.push(st);
d[st]=0;
while(!q.empty()){
int i,k=q.front();
q.pop();
for(i=head[k];~i;i=e[i].next){
int v=e[i].to;
if(e[i].w>0&&d[v]==-1){
d[v]=d[k]+1;
q.push(v);
}
}
}
return d[ed]>0;
}
int dinic(int k,int low){//在k节点有流量low，到终点ed的最大流
if(k==ed||low==0)return low;
int a,res=0;
for(int &i=g[k];~i;i=e[i].next){//这个g就是当前弧优化
int v=e[i].to;
if(d[v]==d[k]+1&&e[i].w>0&&(a=dinic(v,min(low,e[i].w)))){
res+=a;//当前这条弧送了a流量到终点
low-=a;
e[i].w-=a;
e[i^1].w+=a;
if(!low) break;//如果k相连的前面几条弧已经把low那么多流量送到终点，就不需要后面的弧了，下次访问k时就从现在的g[k]这条弧开始增广。
}
}
return res;
}
void solve(){
ans = 0;
while(bfs()) {
memcpy(g,head,sizeof g);//重新计算过层次图后再初始化当前弧g
while(tans=dinic(st, INF)) ans += tans;
}
}
void init(){
cnt=0;
memset(head, -1, sizeof head);
}
int p[N],s[N],ee[N];
int main(){
int t;
scanf("%d",&t);
for(int cas=1;cas<=t;cas++){
printf("Case %d: ",cas);
int n,m;
int pans=0;
init();
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++){
scanf("%d%d%d",&p[i],&s[i],&ee[i]);
add(st,i,p[i]);
pans+=p[i];
for(int j=s[i];j<=ee[i];j++)
add(i,j+n,1);
}
ed=n+501;
for(int i=n+1;i<=n+500;i++){
add(i,ed,m);
}
solve();
if(ans==pans)puts("Yes\n");
else puts("No\n");
}
}
E - Sasha and Array
给定n(\(1\le n\le 10^5\))个数\(a_i\),和m(\(1\le m\le 10^5\))个操作：
1 l r x ：代表[l,r]区间的a都增加x
2 l r：代表求\(\sum_{i=l}^{i=r} fib(a_i)\), fib(i) 为第 i 项Fibonacci （斐波那契）数
对于操作2，输出答案，且对\(10^9+7\)取模。
题解1：
求 fibonacci 时是用矩阵快速幂(矩阵不一定像这样)：
\[\left[\begin{matrix}
fib(n-1) & fib(n)\\
fib(n) & fib(n+1)
\end{matrix}\right]=
\left[\begin{matrix}
fib(n-2) &fib(n-1) \\
fib(n-1) & fib(n)
\end{matrix}\right]
*
\left[\begin{matrix}
0 & 1 \\
1 & 1
\end{matrix}\right]
\]
fib(n-1) & fib(n)\\
fib(n) & fib(n+1)
\end{matrix}\right]=
\left[\begin{matrix}
fib(n-2) &fib(n-1) \\
fib(n-1) & fib(n)
\end{matrix}\right]
*
\left[\begin{matrix}
0 & 1 \\
1 & 1
\end{matrix}\right]
\]
也就是
\[\left[\begin{matrix}
fib(n-1) & fib(n)\\
fib(n) & fib(n+1)
\end{matrix}\right]=
\left[\begin{matrix}
0 & 1 \\
1 & 1
\end{matrix}\right]^{n-1}
\]
fib(n-1) & fib(n)\\
fib(n) & fib(n+1)
\end{matrix}\right]=
\left[\begin{matrix}
0 & 1 \\
1 & 1
\end{matrix}\right]^{n-1}
\]
于是可以用线段树每个节点是矩阵，线段树维护矩阵的和，就可以得到通项和。
我需要注意的是：
- 用long long，否则会爆
- 懒惰标记用法
- 提前算好bv（b矩阵的x次方）
- query不要忘记取模
- 矩阵里的加和乘直接写，而不用for的话，可以-1s。
题解2：
考虑斐波那契数列的通项:
\[f[n]=\frac{(\frac{1+\sqrt 5}{2})^n-(\frac{1-\sqrt 5}{2})^n}{\sqrt 5}
\]
\]
用两个线段树维护两个复数 $a\pm b\sqrt 5 $ 的n次幂的区间和：
- 增加x，则该区间对应的两个次幂分别乘上x次幂。
- 区间求和，即该区间对应的两个次幂相减后的b。因为答案一定是整数，所以相减再除以\(\sqrt 5\) 后，整数部分就是b。
除以2用乘以inv2 （ 2关于MOD的乘法逆元）来表示。这两个复数就是\((inv2,inv2),(inv2,-inv2)\)。
代码1：
#include<cstdio>
#include<cstring>
#define ll long long
#define N 100005
const ll M = 1e9+7;
using namespace std;
struct Mat{
ll a[2][2];
Mat operator + (const Mat &B){
Mat C;
C.a[0][0]=(a[0][0]+B.a[0][0])%M;
C.a[0][1]=(a[0][1]+B.a[0][1])%M;
C.a[1][0]=(a[1][0]+B.a[1][0])%M;
C.a[1][1]=(a[1][1]+B.a[1][1])%M;
return C;
}
Mat operator * (const Mat &B){
Mat C;
C.a[0][0]=(a[0][0]*B.a[0][0]+a[0][1]*B.a[1][0])%M;
C.a[0][1]=(a[0][0]*B.a[1][0]+a[0][1]*B.a[1][1])%M;
C.a[1][0]=(a[1][0]*B.a[0][0]+a[1][1]*B.a[1][0])%M;
C.a[1][1]=(a[1][0]*B.a[1][0]+a[1][1]*B.a[1][1])%M;
return C;
}
}e={1,0,0,1},b={0,1,1,1},bv,tr[N<<2],lz[N<<2];
Mat pow (int t){
Mat C=e,A=b;
while(t){
if(t&1)C=C*A;
A=A*A;
t>>=1;
}
return C;
}
int L[N<<2],R[N<<2];
void pushDown(int x){
tr[x<<1] =tr[x<<1] *lz[x];
tr[x<<1|1]=tr[x<<1|1]*lz[x];
lz[x<<1] =lz[x<<1] *lz[x];
lz[x<<1|1]=lz[x<<1|1]*lz[x];
lz[x]=e;
}
void pushUp(int x){
tr[x]=tr[x<<1]+tr[x<<1|1];
}
void build(int l,int r,int x){
L[x]=l;R[x]=r;
lz[x]=e;
if(l==r){
int a;
scanf("%d",&a);
tr[x]=pow(a-1);
return;
}
int m=l+r>>1;
build(l,m,x<<1);
build(m+1,r,x<<1|1);
pushUp(x);
}
void add(int l,int r,int x,int v){
if(l<=L[x]&&r>=R[x]){
tr[x]=tr[x]*bv;
lz[x]=lz[x]*bv;
return;
}
if(L[x]!=R[x])pushDown(x);
if(l<=R[x<<1])add(l,r,x<<1,v);
if(r>R[x<<1])add(l,r,x<<1|1,v);
pushUp(x);
}
ll query(int l,int r,int x){
if(l>R[x]||r<L[x])return 0;
if(l<=L[x]&&r>=R[x])return tr[x].a[1][1];
if(L[x]!=R[x])pushDown(x);
return (query(l,r,x<<1)+query(l,r,x<<1|1))%M;
}
int main() {
int n,m,l,r,x,op;
scanf("%d %d",&n,&m);
build(1,n,1);
for(int i=1;i<=m;i++){
scanf("%d %d %d",&op, &l, &r);
if(op==1) scanf("%d",&x), bv=pow(x), add(l,r,1,x);
else printf("%lld\n",query(l,r,1));
}
return 0;
}
代码2:
#include <cstdio>
#include <cstring>
#include <algorithm>
#define ll long long
const int N=1e5+5;
const ll M=1e9+7;
const ll inv2=5e8+4;
using namespace std;
struct Num{
ll a,b;
Num():a(1),b(0){}
Num(ll x,ll y):a(x%M),b(y%M){}
Num operator +(const Num &B)const{
return Num(a+B.a,b+B.b);
}
Num operator *(const Num &B)const{
return Num(a*B.a+b*B.b*5,a*B.b+b*B.a);
}
Num operator ^(int t)const{
Num A=(*this),B(1,0);
while(t){if(t&1)B=B*A;A=A*A;t>>=1;}
return B;
}
}eA(inv2,inv2),eB(inv2,-inv2),tr[2][N<<2],lz[2][N<<2];
void pushup(int i,int x){
tr[i][x]=tr[i][x<<1]+tr[i][x<<1|1];
}
void pushdown(int i,int x){
tr[i][x<<1]=tr[i][x<<1]*lz[i][x];
tr[i][x<<1|1]=tr[i][x<<1|1]*lz[i][x];
lz[i][x<<1]=lz[i][x<<1]*lz[i][x];
lz[i][x<<1|1]=lz[i][x<<1|1]*lz[i][x];
lz[i][x].a=1,lz[i][x].b=0;
}
#define ls l,r,L,L+R>>1,x<<1
#define rs l,r,(L+R>>1)+1,R,x<<1|1
void add(int l,int r,int L,int R,int x,int i,Num ad){
if(l>R||L>r)return;
if(l<=L&&R<=r){
tr[i][x]=tr[i][x]*ad;
lz[i][x]=lz[i][x]*ad;
return;
}
if(L!=R) pushdown(i,x);
add(ls,i,ad);add(rs,i,ad);
pushup(i,x);
}
ll query(int l,int r,int L,int R,int x){
if(l>R||L>r)return 0;
if(l<=L&&R<=r)return (tr[0][x].b-tr[1][x].b)%M;
if(L!=R)pushdown(0,x),pushdown(1,x);
return (query(ls)+query(rs))%M;
}
int main(){
int n,m;
scanf("%d%d",&n,&m);
for(int i=1,a;i<=n;i++){
scanf("%d",&a);
add(i,i,1,n,1,0,eA^a);
add(i,i,1,n,1,1,eB^a);
}
for(int i=1,t,l,r,x;i<=m;i++){
scanf("%d%d%d",&t,&l,&r);
if(t==1){
scanf("%d",&x);
add(l,r,1,n,1,0,eA^x);
add(l,r,1,n,1,1,eB^x);
}
else printf("%lld\n",query(l,r,1,n,1));
}
return 0;
}
F - Lena and Queries
3种操作：
1 a b :添加一对数到集合里。
2 i :移除第 i 次操作添加的一对数。
3 q : 询问\(q\cdot x+y\)最大值，(x,y)是当前在集合里的。
给出n(\(1\le n\le 3\cdot 10^5\))次操作，对于3操作输出最大值。
题解：
对于每对数，相当于平面坐标的一个点。它出现的操作区间是[L,R]，L是添加它的操作编号，如果有移除，则R是移除时的操作下标，否则R是n。
全部操作读入后，将点插入所在操作区间的线段树节点。
求\(z=q\cdot x+y\)的最大值，相当于过点(x,y)且斜率为-q的直线\(y=-q\cdot x +z\)的y轴截距最大，则(x,y)一定是凸包上点。用单调栈求凸包，再三分求最大值。
从底向上用线段树维护操作区间里的点形成的凸壳，同时，对在当前区间里的所有3操作，用三分求得在当前区间的凸包点集下，qx+y的最大值，更新一下答案。
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <iostream>
#include <vector>
#define ll long long
#define N 300005
const ll INF = 1LL << 61;
using namespace std;
int t[N],r[N],empty[N];
ll ans[N];
struct Point{
ll x,y;
bool operator <(const Point &B)const{
return x<B.x||(x==B.x&&y<B.y);
}
Point operator -(const Point &B)const{
return (Point){x-B.x,y-B.y};
}
Point operator +(const Point &B)const{
return (Point){x+B.x,y+B.y};
}
ll operator ^(const Point &B)const{
return x*B.y-y*B.x;
}
ll operator *(const Point &B)const{
return x*B.x+y*B.y;
}
}p[N],S[N];
vector<Point> tr[N<<2];
void insert(int l,int r,int L,int R,int o,int v){
if(l<=L&&R<=r){
tr[o].push_back(p[v]);
return;
}
int M=L+R>>1;
if(l<=M)insert(l,r,L,M,o<<1,v);
if(r>M)insert(l,r,M+1,R,o<<1|1,v);
}
void query(int x,int n){
int l=1,r=n;
while(r-l>=3){//三分求最大值
int m1=l+(r-l)/3;
int m2=l+(r-l)*2/3;
if(p[x]*S[m1]<p[x]*S[m2])l=m1;
else r=m2;
}
for(int i=l;i<=r;i++)
ans[x]=max(ans[x],p[x]*S[i]);
}
void solve(int l,int r,int o){
if(l<r){
int m=l+r>>1;
solve(l,m,o<<1);
solve(m+1,r,o<<1|1);
}
sort(tr[o].begin(),tr[o].end());
int top=0;
for(int i=0;i<tr[o].size();i++){
while(top>1&&((S[top]-S[top-1])^(tr[o][i]-S[top]))>=0)top--;
S[++top]=tr[o][i];
}
for(int i=l;i<=r;i++) if(t[i]==3&&!empty[i]) query(i,top);
}
int main() {
int n;
scanf("%d",&n);
for(int i=1,cnt=0,x;i<=n;i++){
scanf("%d",&t[i]);
if(t[i]==1)
scanf("%lld %lld",&p[i].x,&p[i].y), r[i]=n, cnt++;
else if(t[i]==2)
scanf("%d",&x), r[x]=i, cnt--;
else
scanf("%lld",&p[i].x), p[i].y=1LL, empty[i]=(cnt==0), ans[i]=-INF;
}
for(int i=1;i<=n;i++)if(t[i]==1&&i+1<=r[i]) insert(i,r[i],1,n,1,i);
solve(1,n,1);
for(int i=1;i<=n;i++)if(t[i]==3){
if(empty[i]) puts("EMPTY SET");
else printf("%lld\n",ans[i]);
}
return 0;
}
G - Pouring Rain
下雨使水上升的速度：\(e\ cm/s\)
喝水使水减少的速度：\(v\ cm^3/s\)
杯子的直径：\(d\ cm\)
杯子里水的初始高度：\(h\ cm\)
求若能喝完水，需要多少秒。
#include<cstdio>
#include<cmath>
#define pi acos(-1.0)
using namespace std;
double d,h,v,e;
int main() {
scanf("%lf%lf%lf%lf",&d,&h,&v,&e);
double s=v/pi/(d/2)/(d/2)-e;
if(s>0)printf("YES\n%f",h/s);
else puts("NO");
return 0;
}
H - Constellation
给定n个点，求可组成一个三角形且内部没有其它点的三个点。
将点按x，再按y排序。选取第一第二个点，再输出不和它们构成直线的第一个点。
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#define ll long long
#define N 100005
using namespace std;
struct star{
ll x,y;int id;
}s[N];
int n;
int cmp(star a,star b){
return a.x<b.x||a.x==b.x&&a.y<b.y;
}
int main() {
scanf("%d",&n);
for(int i=1;i<=n;i++){
scanf("%lld%lld",&s[i].x,&s[i].y);
s[i].id=i;
}
sort(s+1,s+1+n,cmp);
printf("%d %d ",s[1].id,s[2].id);
for(int i=3;i<=n;i++){
if((s[1].x-s[2].x)*(s[2].y-s[i].y)!=(s[1].y-s[2].y)*(s[2].x-s[i].x)){
printf("%d",s[i].id);break;
}
}
return 0;
}