Codeforces Round #791 (Div. 2)
A. AvtoBus
题目链接：Problem - A - Codeforces
样例输入：
4
4
7
24
998244353998244352
样例输出：
1 1
-1
4 6
166374058999707392 249561088499561088
简化题意：给定n，求解满足方程4*x+6*y=n的x+y的最大值和最小值。
分析：显然发现对于n是奇数或者n小于4的情况是无解的，其余情况都是有解的，对于求解最大值的情况我们就是尽量的用4去构造n，实在不行了再用6去构造，而求解最小值则刚好相反。
分类讨论以下就行：
#include<iostream>
#include<algorithm>
#include<cstring>
#include<cstdio>
#include<cmath>
#include<vector>
#include<queue>
using namespace std;
const int N=2e5+10;
int main()
{
int T;
cin>>T;
long long n;
while(T--)
{
scanf("%lld",&n);
long long l,r;
if(n<4||n&1) puts("-1");
else
{
if(n%6==0) l=n/6;
else l=n/6+1;
r=n/4;
printf("%lld %lld\n",l,r);
}
}
return 0;
}B. Stone Age Problem
题目链接：Problem - B - Codeforces
样例输入：
5 5
1 2 3 4 5
1 1 5
2 10
1 5 11
1 4 1
2 1
样例输出：
19
50
51
42
5
题意：给定一个长度为n的数组，我们有两种操作，一种操作是选定一个位置让后将该位置的值变为val。另一种操作是把整个数组的值全部变为val，每次操作后输出数组中所有元素的和。
分析：其实这道题用线段树可以直接切掉，但是作为cf的B题完全没必要实现线段树，我们用一个last[i]记录第i个位置上的数上一次被单独操作的时间即可，我们还需要记录一下上一次对整个数组进行操作的时间和值，这样我们就能够通过判断这两个时间的早晚来确定当前位置的值了。
#include<iostream>
#include<algorithm>
#include<cstring>
#include<cstdio>
#include<cmath>
#include<vector>
#include<queue>
using namespace std;
const int N=2e5+10;
int a[N];
int last[N];
int main()
{
int n,q;
cin>>n>>q;
long long ans=0;
for(int i=1;i<=n;i++)
scanf("%d",&a[i]),ans+=a[i];
int id=0,res;
for(int i=1;i<=q;i++)
{
int op,pos,val;
scanf("%d",&op);
if(op==1)
{
scanf("%d%d",&pos,&val);
if(last[pos]<id)
ans+=val-res;
else
ans+=val-a[pos];
last[pos]=i;
a[pos]=val;
}
else
{
scanf("%d",&res);
id=i;ans=1ll*res*n;
}
printf("%lld\n",ans);
}
return 0;
}C. Rooks Defenders
题目链接：Problem - C - Codeforces
样例输入：
8 10
1 2 4
3 6 2 7 2
1 3 2
3 6 2 7 2
1 4 3
3 2 6 4 8
2 4 3
3 2 6 4 8
1 4 8
3 2 6 4 8
样例输出：
No
Yes
Yes
No
Yes
题意：给定一个n*n的方形格子，其中我们可以对格子进行操作和询问，对于格子的操作有两种，一种是在某个位置上放置一个炸弹，另一种操作是取下某个位置的炸弹，取下某个位置的炸弹的前提就是当前位置存在炸弹，每个炸弹都有一个攻击范围，就是该炸弹所在的行和列，我们现在来进行询问，每次询问给出一个矩形的左上角和右下角的坐标，问我们当前方格中的炸弹能不能把矩形中所有格子都炸掉。
分析：这道题我们直接用树状数组维护一下哪些行和哪些列存在炸弹即可，一个x*y的矩形能够被完全炸掉当且仅当该矩形所有的行或者所有的列都有炸弹，所以我们可以用树状数组维护一下，但是需要注意的一点就是我们不能只询问某些行或者某些列有多少炸弹，因为可能存在某些行不止一个炸弹，所以我们可以用两个树状数组进行相互维护，细节见代码：
#include<iostream>
#include<algorithm>
#include<cstring>
#include<cstdio>
#include<cmath>
#include<vector>
#include<queue>
using namespace std;
const int N=2e5+10;
int r[N],c[N];
int rr[N],cc[N];
int lowbit(int x)
{
return x&-x;
}
void addr(int x,int val)
{
for(int i=x;i<N;i+=lowbit(i)) r[i]+=val;
}
void addc(int x,int val)
{
for(int i=x;i<N;i+=lowbit(i)) c[i]+=val;
}
long long sumr(int x)
{
int sum=0;
for(int i=x;i;i-=lowbit(i)) sum+=r[i];
return sum;
}
long long sumc(int x)
{
int sum=0;
for(int i=x;i;i-=lowbit(i)) sum+=c[i];
return sum;
}
void addrr(int x,int val)
{
for(int i=x;i<N;i+=lowbit(i)) rr[i]+=val;
}
void addcc(int x,int val)
{
for(int i=x;i<N;i+=lowbit(i)) cc[i]+=val;
}
long long sumrr(int x)
{
int sum=0;
for(int i=x;i;i-=lowbit(i)) sum+=rr[i];
return sum;
}
long long sumcc(int x)
{
int sum=0;
for(int i=x;i;i-=lowbit(i)) sum+=cc[i];
return sum;
}
int main()
{
int n,m;
cin>>n>>m;
while(m--)
{
int op;
scanf("%d",&op);
int x,y;
if(op==1)
{
scanf("%d%d",&x,&y);
addr(x,1);addc(y,1);
if(sumr(x)-sumr(x-1)==1) addrr(x,1);
if(sumc(y)-sumc(y-1)==1) addcc(y,1);
}
else if(op==2)
{
scanf("%d%d",&x,&y);
addr(x,-1);addc(y,-1);
if(sumr(x)-sumr(x-1)==0) addrr(x,-1);
if(sumc(y)-sumc(y-1)==0) addcc(y,-1);
}
else
{
int x1,x2,y1,y2;
scanf("%d%d%d%d",&x1,&y1,&x2,&y2);
if(sumrr(x2)-sumrr(x1-1)==(x2-x1+1)) puts("YES");
else if(sumcc(y2)-sumcc(y1-1)==(y2-y1+1)) puts("YES");
else puts("NO");
}
}
return 0;
}D. Toss a Coin to Your Graph...
题目链接：Problem - D - Codeforces
样例输入：
6 7 4
1 10 2 3 4 5
1 2
1 3
3 4
4 5
5 6
6 2
2 5
样例输出：
6 7 100
1 10 2 3 4 5
1 2
1 3
3 4
4 5
5 6
6 2
2 5
题意：给定一个n个点m条边的有向图，每个点都有一个点权，然后让我们求得一个长度为k-1的路径使得值为这条路径上所有点权的最大值，而我们要输出这个最大值的最小值，不存在则输出-1。
分析：一般求解最大值的最小值我们肯定第一感觉想到的就是二分，对于这道题我们可以对答案进行二分，假如我们判断是否存在一个最大值小于等于x的满足题意的路径我们可以只考虑那些点权小于等于x的点，并把与这些点有关的边加到图中，然后我们看一下这个图中是否有长度为k-1的路径即可，如果有环则一定存在长度为k-1的路径，否则我们直接用拓扑排序求一下图中最远两个点之间的距离，判断其与k-1的关系即可。细节见代码：
#include<iostream>
#include<algorithm>
#include<cstring>
#include<cstdio>
#include<cmath>
#include<vector>
#include<queue>
using namespace std;
const int N=2e5+10;
int a[N];
bool vis[N];
vector<int>tp[N];
vector<int>p[N];
int du[N],f[N];
int n,m,k;
bool bfs(int x)
{
int mx=0;
queue<int>q;
int cnt=0;//记录出队结点个数
for(int i=1;i<=n;i++)
{
if((!du[i])&&(a[i]<=x)) q.push(i);
if(a[i]<=x) cnt++;
}
if(!cnt) return false;//注意特判空图的情况
while(!q.empty())
{
int t=q.front();
q.pop();
cnt--;
for(int i=0;i<p[t].size();i++)
{
int j=p[t][i];
f[j]=f[t]+1;
mx=max(f[j],mx);
du[j]--;
if(!du[j]) q.push(j);
}
}
if(cnt) return true;//存在环
if(mx>=k-1) return true;//存在长度大于等于k-1的路径
return false;
}
int main()
{
cin>>n>>m>>k;
for(int i=1;i<=n;i++) scanf("%d",&a[i]);
for(int i=1;i<=m;i++)
{
int u,v;
scanf("%d%d",&u,&v);
tp[u].push_back(v);
}
int l=0,r=1e9+1;
while(l<r)
{
int mid=l+r>>1;
for(int i=1;i<=n;i++) p[i].clear(),f[i]=du[i]=0,vis[i]=false;
for(int i=1;i<=n;i++)
{
if(a[i]>mid) continue;
for(int j=0;j<tp[i].size();j++)
if(a[tp[i][j]]<=mid) p[i].push_back(tp[i][j]),du[tp[i][j]]++;
}
if(bfs(mid)) r=mid;
else l=mid+1;
}
printf("%d",l==(1e9+1)?-1:l);
return 0;
}