前言

传送门 :

A - AvtoBus

题意 :
给定一个数$n$,询问$a\*4+b\*6=n$其中$a+b$的最大最小值

思路 :

$$\begin{aligned} & a\*4+b\*6=n\\\ & 6\*(a+b)=(n+2\*a)\\\ & (a+b)=\frac{n+2\*a}{6}\\\ & \ \ \ \ \ \ \ \ \ 同理可得\\\ &(a+b)=\frac{n-2\*b}{4} \end{aligned}$$

因此我们可以得知
- $n$是奇数的时候无解
- 特判$n=2$

显然的最小值就是$n+2*a==n$的时候,当然需要判断是否能够整除

最大值就是$n-2*b==n$的时候,因为除法本身就有向下取整,因此无需特判

code :

void solve(){
    ll n;cin>>n;
    if(n%2 || n == 2){
        cout<<-1<<endl;
        return;
    }

    ll minn = n/6 ;
    if(n%6) minn++;

    ll maxn = n/4;


    cout<<minn<<" "<<maxn<<endl;

}

B. Stone Age Problem

题意 :
给定一个$a[]$,对于每次操作都给一个数组的和

操作定义如下 ：
- $x,k$将$a[x]=k$
- $k$所有的$a[i]=k$

思路 :
显然的区间修改,区间求和,单点修改要是有积累板子的习惯这题就秒了

当然我们也也可以使用$map$进行模拟

模拟过程看代码
code :

struct node{
    int to,val;
};

ll tr[N];
int n,m;
int st[N];
int w[N];

void solve(){
    cin>>n>>m;
    ll total = 0;
    for(int i=1;i<=n;i++){
        cin>>w[i];
        total+=w[i];
        mp[i] = w[i];

    }



    int pre = 0 ;

    while(m -- ){
        int op;cin>>op;
        if(op == 1){
            int x,k;cin>>x>>k;
            total += k -  (mp[x]?mp[x]:pre);
            mp[x] = k;
        }else{
            ll  x;cin>>x;
            total = x*n;
            pre = x;
            mp.clear();

        }
        cout<<total<<endl;

    }


}

C - Rooks Defenders

题意 :
给定一个$n*m$的方格对于询问进行修改或回答

操作 :

• 将$g[x][y]-\-$
• 将$g[x][y]++$
• 给定一个矩阵,询问是否 每行都存在$g[i][y]$不为零或者$g[x][j]$不为0

思路 :
这道题和 https://www.luogu.com.cn/problem/P3801同理
都是使用 两个树状数组进行维护

不过这题不同那题的是,一个是点修改一个是行列修改

但是我们操作原理相同

使用树状数组维护,处理方法类似于二维前缀和

code :

const int N = 2e5+10,INF = 0x3f3f3f3f;
const double eps = 1e-5;


struct node{
    int to,val;
};

#define int long long

ll Tx[N],Ty[N];
int n,m,q;
int stx[N],sty[N];

int lowbit(int x){
    return x & -x;
}
void add(ll *C,int x,int k){

    for(int i = x; i < N ;i+=lowbit(i)){
        C[i]+=k;
    }
}
ll query(ll  *C,int x){
    int sum = 0 ;
    for(int i = x ;i; i -= lowbit(i)){
        sum+=C[i];
    }
    return sum;
}

void solve(){
    cin>>n>>q;
    while(q -- ){
        int op;cin>>op;
        if(op == 1){
            int x,y;cin>>x>>y;
            if(stx[x] == 0) add(Tx,x,1);
            if(sty[y] == 0) add(Ty,y,1);

            stx[x]++;
            sty[y]++;
        }else if(op == 2){
            int x,y;cin>>x>>y;

            stx[x] -- ;
            sty[y] -- ;
            if(stx[x] == 0)add(Tx,x,-1);
            if(sty[y] == 0)add(Ty,y,-1);
        }else {
            int x1,y1,x2,y2;
            cin>>x1>>y1>>x2>>y2;

            int totalx = query(Tx,x2) - query(Tx,x1-1);
            int totaly = query(Ty,y2) - query(Ty,y1-1);
            if(totalx >= x2 - x1+1) cout<<"Yes"<<endl;
            else if(totaly >= y2-y1+1)cout<<"Yes"<<endl;
            else cout<<"No"<<endl;

        }
    }
}

signed main(){
    IOS
    CIT
    COT
    //int t;cin>>t;while(t--)
    solve();
    return 0 ;
}

D. Toss a Coin to Your Graph…

题意 :
给定一个有向图,每个点权值$a[i]$,询问是否有一条长度为$k$的路径,输出其路径上权值最大值的最小可能

思路 :
最大值最小显然的这题首先需要二分出$x$

然后我们再将所有满足条件的边进行操作

显然如果该图是有环的话,那么这个答案必然是$return\ true$的,

否则我们可以采用$dp$求得最长链

对于有向图的环问题,我们可以采用拓扑排序

处理方法同于 https://www.acwing.com/problem/content/description/3816/

Code :

// Problem: D. Toss a Coin to Your Graph...
// Contest: Codeforces - Codeforces Round #791 (Div. 2)
// URL: https://codeforces.com/contest/1679/problem/D
// Memory Limit: 256 MB
// Time Limit: 3000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#include <iostream>
#include <vector>
#include <map>
#include <cstring>
#include <queue>
#include <math.h>
#include <set>
#include <stack>
#include <algorithm>
using namespace std;
#define IOS  ios::sync_with_stdio(false);
#define CIT  cin.tie(0);
#define COT  cout.tie(0);

#define int long long
#define ll long long
#define x first
#define y second
#define pb push_back
#define endl '\n'
#define all(x) (x).begin(),x.end()
#define Fup(i,a,b) for(int i=a;i<=b;i++)
#define Fde(i,a,b) for(int i=a;i>=b;i--)

typedef priority_queue<int,vector<int>,greater<int>>  Pri_m;
typedef pair<int,int> pii;
typedef vector<int> VI;
map<int,int> mp;
const int N = 2e5+10,INF = 0x3f3f3f3f;
const double eps = 1e-5;


struct node{
    int to,val;
};

int n,m,k;
int a[N];
vector<int> g[N];
vector<pii> edg;

int deg[N];
int flag[N];
int dp[N];

bool check(int x){
    for(int i=1;i<=n;i++)
    deg[i] = 0 ,flag[i] = 0,dp[i] = -INF;


    for(auto t : edg){
        if(a[t.x] <= x && a[t.y] <= x) deg[t.y]++;
    }

    for(int i=1;i<=n;i++)
    if(a[i]<=x)flag[i] = 1,dp[i] = 1;

    queue<int> q;

    for(int i=1;i<=n;i++){
        if(flag[i] && !deg[i])q.push(i);
    }

    while(q.size()){
        auto t = q.front();
        q.pop();

        for(auto j : g[t]){
            if(!flag[j]) continue;
            dp[j] = max(dp[j],dp[t]+1);
            if(dp[j]>=k)return true;
            deg[j]--;
            if(!deg[j])q.push(j);
        }
    }

    for(int i=1;i<=n;i++){
        if(flag[i] && deg[i]) return true;
    }


    return false;

}
void solve(){
    cin>>n>>m>>k;
    ll maxn = -INF;

    for(int i=1;i<=n;i++) cin>>a[i],maxn = max(maxn,a[i]);
    for(int i=1;i<=m;i++){
        int u,v;cin>>u>>v;
        g[u].pb(v);
        edg.pb({u,v});
    }

    int l = 0 ,r = 1e9+1;

    int ans = INF;
    if(k == 1){
        cout<<maxn<<endl;
        return;
    }

    while(l<=r){
        int mid = (l+r)/2;
        if(check(mid)){
            ans = min(ans,mid);
            r = mid-1;
        }else l = mid+1;
    }

    if(ans == INF)cout<<-1<<endl;
    else cout<<ans<<endl;

}

signed main(){
    //int t;cin>>t;while(t--)
    solve();
    return 0 ;
}