A 最短路

待补

B组队

排序后,二分大于当前这个数的第一个位置,更新最大值即可
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define me(a,x) memset(a,x,sizeof a)
#define rep(i,x,n) for(int i=x;i<n;i++)
#define repd(i,x,n) for(int i=x;i<=n;i++)
#define all(x) (x).begin(), (x).end()
#define pb(a) push_back(a)
#define paii pair<int,int>
#define pali pair<ll,int>
#define pail pair<int,ll>
#define pall pair<ll,ll>
#define x first
#define y second
int main()
{
    int t;cin>>t;
    while(t--){
        int n,k;cin>>n>>k;
        vector<ll> a(n+1);
        map<ll,int> mp;
        ll ma=-2e9,mi=2e9;
        for(int i=1;i<=n;i++) cin>>a[i],ma=max(ma,a[i]),mi=min(mi,a[i]);
        sort(a.begin()+1,a.end());
        int ans=0;
        for(int i=1;i<=n;i++){
            int p=upper_bound(a.begin()+1,a.end(),a[i]+k)-a.begin();
            ans=max(ans,p-i);
        }
        cout<<ans<<endl;
 
    }
   return 0;
}


C十面埋伏

对‘#’外围的'.'全都打上标记,然后看标记的周围是不是有’#',有的话变成‘*’即可
#include<bits/stdc++.h>
using namespace std;
int n,m;
char s[505][505];
bool vis[505][505];
int dx[]={1,-1,0,0};
int dy[]={0,0,1,-1};
int check(int x,int y){
    if(x<0 || x>=n || y<0 || y>=m || vis[x][y] || s[x][y]=='#') return 1;
    return 0;
}
void dfs(int x,int y){
    vis[x][y]=1;
    for(int i=0;i<4;i++){
        int fx=x+dx[i],fy=y+dy[i];
        if(check(fx,fy)) continue;
        dfs(fx,fy);
    }
}
int main(){
    cin>>n>>m;
    for(int i=0;i<n;i++)  cin>>s[i];
    dfs(0,0);
    for(int i=0;i<n;i++){
        for(int j=0;j<m;j++){
            if(vis[i][j]){
                 int cnt=0;
                if(i>=1 && s[i-1][j]=='#') cnt++;
                if(j>=1 && s[i][j-1]=='#') cnt++;
                if(i+1<n && s[i+1][j]=='#')  cnt++;
                if(j+1<m && s[i][j+1]=='#') cnt++;
                if(cnt) s[i][j]='*';
 
            }
        }
    }
    for(int i=0;i<n;i++) cout<<s[i]<<endl;
    return 0;
}


D牛妹吃豆子

二维差分+二维前缀和
#include<bits/stdc++.h>
typedef long long ll;
using namespace std;
ll c[2005][2005],n,m;
int main()
{
    ios::sync_with_stdio(0);
    int k,q;cin>>n>>m>>k>>q;
    while(k--){
        int x1,y1,x2,y2;
        cin>>x1>>y1>>x2>>y2;
        c[x1][y1]++;
        c[x2+1][y2+1]++;
        c[x1][y2+1]--;
        c[x2+1][y1]--;
    }
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            c[i][j]+=c[i-1][j]+c[i][j-1]-c[i-1][j-1];
        }
    }

    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            c[i][j]+=c[i-1][j]+c[i][j-1]-c[i-1][j-1];
        }
    }

    while(q--){
        int x1,y1,x2,y2;
        cin>>x1>>y1>>x2>>y2;
        cout<<c[x2][y2]-c[x1-1][y2]-c[x2][y1-1]+c[x1-1][y1-1]<<endl;

    }

   return 0;
}


E旅旅旅游

正反分别跑一次最短路,枚举每条边是不是最短路的必经的边,不是的话,并查集合并点集,最后看是不是1~n在同一个集合
#include <bits/stdc++.h>
typedef long long ll;
using namespace std;
ll n, m;
ll f[1<<17];
ll find(ll x){
    return f[x]==x?x:f[x]=find(f[x]);
}
struct dijkstra
{   
    struct node
    {
        ll to, cost;
        friend bool operator<(node a, node b)
        {
        return a.cost > b.cost;
        }
    };
    ll d[1<<17];
    ll e[1<<20], v[1<<20], ne[1<<20], h[1<<20], idx;
    bool vis[1<<17];
    void Init()
    {
        memset(h, -1, sizeof h);
    }
    void add(ll a, ll b, ll c)
    {
        e[idx] = b, v[idx] = c, ne[idx] = h[a], h[a] = idx++;
    }
    void dj(ll x, ll y)
    {

        for (ll i = 1; i <= n; i++)
            d[i] = -1, vis[i] = 0;
        priority_queue<node> q;
        q.push({x, 0});
        while (!q.empty())
        {
            node now = q.top();
            q.pop();
            if (!vis[now.to])
            {
                vis[now.to] = 1;
                d[now.to] = now.cost;
                for (ll i = h[now.to]; i != -1; i = ne[i])
                {
                    node next;
                    next.to = e[i];
                    next.cost = now.cost + v[i];
                    if (!vis[next.to])
                        q.push(next);
                }
            }
        }
    }
} a,b;
int main()
{
    ios::sync_with_stdio(0);
    cin>>n>>m;
    for(ll i=1;i<=n;i++) f[i]=i;
    a.Init(),b.Init();
    for(ll i=1; i<=m; i++)
    {
        ll x,y,d;
        cin>>x>>y>>d;
        a.add(x,y,d),a.add(y,x,d);
        b.add(x,y,d),b.add(y,x,d);
    }
    a.dj(1,n);
    b.dj(n,1);
    ll mi=a.d[n];
    for(ll i=1;i<=n;i++){

        for(ll j=a.h[i];~j;j=a.ne[j]){
            if(mi==a.d[i]+b.d[a.e[j]]+a.v[j] || mi==a.d[a.e[j]]+b.d[i]+a.v[j]) continue;
             f[find(i)]=find(a.e[j]);
        }
    }
    ll fa=find(1);
    ll num=1;
    for(ll i=1;i<=n;i++) if(fa!=find(i)) num++;
    cout<<(num==1?"YES":"NO")<<endl;
    return 0;
}


F斗兽棋

签到
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define me(a,x) memset(a,x,sizeof a)
#define rep(i,x,n) for(int i=x;i<n;i++)
#define repd(i,x,n) for(int i=x;i<=n;i++)
#define all(x) (x).begin(), (x).end()
#define pb(a) push_back(a)
#define paii pair<int,int>
#define pali pair<ll,int>
#define pail pair<int,ll>
#define pall pair<ll,ll>
#define x first
#define y second
int main()
{
    string a,b;
    cin>>a>>b;
    if(b=="elephant"&&a=="tiger" || b=="tiger"&&a=="cat" || b=="cat"&&a=="mouse" || b=="mouse"&&a=="elephant")
        cout<<"tiangou txdy";
    else cout<<"tiangou yiwusuoyou";
    
   return 0;
}


G做题

排序后从最小的开始取
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define me(a,x) memset(a,x,sizeof a)
#define rep(i,x,n) for(int i=x;i<n;i++)
#define repd(i,x,n) for(int i=x;i<=n;i++)
#define all(x) (x).begin(), (x).end()
#define pb(a) push_back(a)
#define paii pair<int,int>
#define pali pair<ll,int>
#define pail pair<int,ll>
#define pall pair<ll,ll>
#define x first
#define y second
int main()
{
 
    ll n,k;
    cin>>n>>k;
    vector<ll> a(n+1);
    for(int i=1; i<=n; i++)cin>>a[i];
    sort(a.begin()+1,a.end());
    int ans=0;
    for(int i=1;i<=n;i++){
        if(k>=a[i]){
            ans++;k-=a[i];
        }
    }
    cout<<ans<<endl;
 
 
    return 0;
}


H人人都是好朋友

离散化后,对于朋友进行集合合并,把朋友处理完后,对敌人进行查询是不是在同一个集合
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define me(a,x) memset(a,x,sizeof a)
#define rep(i,x,n) for(int i=x;i<n;i++)
#define repd(i,x,n) for(int i=x;i<=n;i++)
#define all(x) (x).begin(), (x).end()
#define pb(a) push_back(a)
#define paii pair<int,int>
#define pali pair<ll,int>
#define pail pair<int,ll>
#define pall pair<ll,ll>
#define x first
#define y second
#define rson mid + 1, r, rt << 1 | 1
#define lson l, mid, rt << 1
const ll maxn=1e6+5;
int f[maxn<<1];
struct node
{
    int a,b,c;
}a[maxn],b[maxn];
int q[maxn<<1];
int find(int x){
    return f[x]==x?x:f[x]=find(f[x]);
}
void join(int x,int y){
    x=find(x),y=find(y);
    if(x!=y) f[x]=y;
}

int main() {
    ios::sync_with_stdio(0);
    int t;cin>>t;
    while(t--){
        int n;cin>>n;
        int cnt=0;
        for(int i=1;i<=n;i++) cin>>a[i].a>>a[i].b>>a[i].c,q[++cnt]=a[i].a,q[++cnt]=a[i].b;
        sort(q+1,q+1+cnt);
        int len=unique(q+1,q+1+cnt)-q-1;
        for(int i=1;i<=(n<<1);i++) f[i]=i;
        cnt=0;
        for(int i=1;i<=n;i++){
            int x=lower_bound(q+1,q+len+1,a[i].a)-q;
            int y=lower_bound(q+1,q+len+1,a[i].b)-q;
            int id=a[i].c;
            if(id==1) {
                join(x,y);
            }
            else b[++cnt]={x,y,id};
        }
        int flag=0;
         for(int i=1;i<=cnt;i++){
            if(find(b[i].a)==find(b[i].b)){
                flag=1;break;
            }
        }
        if(flag) cout<<"NO"<<endl;
        else cout<<"YES"<<endl;

    }
    return 0;
}


I求和

树上操作,而且只是单点更新和区间求和。
dfs序把树形结构变为线性结构,树状数组维护即可。
如果有区间更新套线段树即可
#include<cstring>
#include<vector>
#include<cstdio>
using namespace std;
typedef long long ll;
ll a[1<<20];
ll c[1<<20],in[1<<20],out[1<<20];
ll time;
ll n,q,root;
ll tot,head[1<<21];
struct node {
    ll to, next;
} edge[1<<21];
void add(ll u, ll v) {
    edge[tot].to = v;
    edge[tot].next = head[u];
    head[u] = tot++;
}
void up(ll x,ll v){
    for(;x<=n;x+=x&(-x)) c[x]+=v;
}
ll get(ll x){
    ll ans=0;
    for(;x;x-=x&(-x)) ans+=c[x];
    return ans;
}
void dfs(ll x,ll f){
    in[x]=++time;
    for (ll i = head[x]; i != -1; i = edge[i].next){
        ll it=edge[i].to;
        if(it==f) continue;
        dfs(it,x);
    }
    out[x]=time;
}
int main(){
    memset(head,-1,sizeof head);
    scanf("%lld%lld%lld",&n,&q,&root);
    for(ll i=1;i<=n;i++) scanf("%lld",&a[i]);
    for(ll i=1;i<n;i++){
        ll x,y;scanf("%lld%dll",&x,&y);
        add(x,y),add(y,x);
    }
    dfs(root,-1);
    for(ll i=1;i<=n;i++) up(in[i],a[i]);
    while(q--){
        ll op,x;scanf("%lld%lld",&op,&x);
        if(op==1){
            ll y;scanf("%lld",&y);
            up(in[x],y);
        }
        else printf("%lld\n",get(out[x])-get(in[x]-1));
    }
    return 0;
}


J建设道路

简单数学推公式
两两之间进行计算,也就是有种,那么因为每种都会处理出来两个平方项,总共就处理出来了
总共有n个点,所有每个点的平方和进行增加了n-1次
考虑减去的  对于下标为1的时候减去的是
对于下标为2减去的就是
显然处理一个后缀和遍历即可。注意取模
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define me(a,x) memset(a,x,sizeof a)
#define rep(i,x,n) for(int i=x;i<n;i++)
#define repd(i,x,n) for(int i=x;i<=n;i++)
#define all(x) (x).begin(), (x).end()
#define pb(a) push_back(a)
#define paii pair<int,int>
#define pali pair<ll,int>
#define pail pair<int,ll>
#define pall pair<ll,ll>
#define x first
#define y second
const ll mod=1e9+7;
ll a[1<<20];
int main()
{
    int n;cin>>n;
    ll sum=0;
    for(int i=1;i<=n;i++)cin>>a[i],sum=(sum+(n-1)*a[i]%mod*(a[i]%mod))%mod;
    for(int i=n-1;i;i--){
        sum=((sum-((2*a[i])%mod*(a[i+1]%mod)%mod))%mod+mod)%mod;
        a[i]+=a[i+1];
    }
    cout<<(sum%mod+mod)%mod;

   return 0;
}