---

layout: post
title: Codeforces Round 261(Div. 2)
author: "luowentaoaa"
catalog: true
tags:
mathjax: true
- codeforces
- dp

---

传送门

A - Pashmak and Garden （签到）

题意

对于一个正方形给你其中两个点，让你输出另外两个点

思路

水

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod=1e9+7;
const int maxn=1e5+50;
const int inf=1e9;
typedef unsigned long long ull;

int main()
{
    std::ios::sync_with_stdio(false);
    std::cin.tie(0);
    std::cout.tie(0);
    int x1,x2,y1,y2;
    cin>>x1>>y1>>x2>>y2;

    if(x1==x2){
        int dis=abs(y1-y2);
        cout<<x1+dis<<" "<<y1<<" ";
        cout<<x2+dis<<" "<<y2<<endl;
    }
    else if(y1==y2){
        int dis=abs(x1-x2);
        cout<<x1<<" "<<y1+dis<<" ";
        cout<<x2<<" "<<y2+dis<<endl;
    }
    else{
        int dis1=abs(x1-x2);
        int dis2=abs(y1-y2);
        if(dis1!=dis2)puts("-1");
        else{
            cout<<x2<<" "<<y1<<" ";
            cout<<x1<<" "<<y2<<endl;
        }
    }
    return 0;
}

B - Pashmak and Flowers （水题）

题意

一堆数，找出两个数使得差值最大，输出这两个数有多少种选择

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod=1e9+7;
const int maxn=2e5+50;
const int inf=1e9;
typedef unsigned long long ull;
int a[maxn];
int main()
{
    std::ios::sync_with_stdio(false);
    std::cin.tie(0);
    std::cout.tie(0);
    int n;
    cin>>n;
    int mx=-(1e9+7),mi=1e9+7;
    int aa=0,bb=0;
    for(int i=1;i<=n;i++){
        cin>>a[i];
        mx=max(mx,a[i]);
        mi=min(mi,a[i]);
    }
    for(int i=1;i<=n;i++){
        if(a[i]==mx)aa++;
        if(a[i]==mi)bb++;
    }
    cout<<abs(mx-mi)<<" "<<(ll)(mx==mi?1LL*aa*(aa-1)/2LL*1LL:1LL*aa*bb)<<endl;
    return 0;
}

C - Pashmak and Buses (dfs 暴力)

题意

n个人m天k个车每个人每天都要坐车，要不能出现任意两个人m天做的车都一样

思路

相当于不能有两个长度为m的字符串完全相同

#include<iostream>
#include<algorithm>
#include<string>
#include<queue>
#include<cstring>
using namespace std;
typedef long long ll;
const ll mod=1e9+7;
const int maxn=2e5+50;
const int inf=1e9;
typedef unsigned long long ull;
ll n,d,k;
int a[1100][1100];
int now[1100];
int cnt;
void dfs(int pos){
    if(pos==d+1){
        cnt++;
        for(int i=1;i<=d;i++)a[i][cnt]=now[i];
        return;
    }
    for(int i=1;i<=k;i++){
        now[pos]=i;
        dfs(pos+1);
        if(cnt>=n)return;
    }
}
int main()
{
    std::ios::sync_with_stdio(false);
    std::cin.tie(0);
    std::cout.tie(0);
    cin>>n>>k>>d;
    int kk=1;
    bool flag=false;
    for(int i=1;i<=d;i++){
        kk*=k;
        if(kk>=n){flag=1;break;}
    }
    if(!flag)puts("-1"),exit(0);
    dfs(1);
    for(int i=1;i<=d;i++){
        for(int j=1;j<=n;j++)
            cout<<a[i][j]<<" ";
        cout<<endl;
    }

    return 0;
}

D - Pashmak and Parmida's problem (树状数组)

题意

定义
\[ f(l,r,x)=区间[l,r]中值等于x的个数 \]
求有多少对
\[ f(1,i,ai)>f(j,n,aj) \]

思路

直接维护从后向前的值，然后从前往后遍历 查找后面小于它的值

树状数组维护

#include<iostream>
#include<algorithm>
#include<string>
#include<queue>
#include<cstring>
#include<unordered_map>
using namespace std;
typedef long long ll;
const ll mod=1e9+7;
const int maxn=2e6+50;
const int inf=1e9;
typedef unsigned long long ull;
int a[maxn];
int c[maxn];
int lowbit(int x){
    return x&(-x);
}
int add(int x,int value){
    for(;x<maxn;x+=lowbit(x))c[x]+=value;
}
int query(int x){
    int ans=0;
    for(;x;x-=lowbit(x))ans+=c[x];
    return ans;
}
unordered_map<int,int>pre,suf;
ll ans;
int main()
{
    std::ios::sync_with_stdio(false);
    std::cin.tie(0);
    std::cout.tie(0);
    int n;
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>a[i];
    }
    for(int i=n;i;i--){
        suf[a[i]]++;
        add(suf[a[i]],1);
    }
    for(int i=1;i<=n;i++){
        pre[a[i]]++;
        add(suf[a[i]],-1);
        suf[a[i]]--;
        ans+=1LL*query(pre[a[i]]-1);
    }
    cout<<ans<<endl;
    return 0;
}

E - Pashmak and Graph (dp)

题意

给出一个有向图找出一个最长不简单路使得路径长度严格递增

思路

模拟一维做法，排序一个边，然后注意一下相等的情况

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod=1e9+7;
const int maxn=3e5+50;
const int inf=1e9;
typedef unsigned long long ull;
struct node{
    int u,v,w;
    bool operator<(const node &a)const{
        return w<a.w;
    }
}my[maxn];
int d[maxn];
int dp[maxn];
int main()
{
    std::ios::sync_with_stdio(false);
    std::cin.tie(0);
    std::cout.tie(0);

    int n,m;
    cin>>n>>m;
    for(int i=1;i<=m;i++){
        cin>>my[i].u>>my[i].v>>my[i].w;
    }
    sort(my+1,my+1+m);
    for(int i=1;i<=m;i++){
        int u=my[i].u;
        int v=my[i].v;
        int w=my[i].w;
        int j=i+1;
        while(j<=m&&my[j].w==w)j++;
        stack<int>st;
        for(int k=i;k<j;k++){
            d[my[k].v]=max(d[my[k].v],dp[my[k].u]+1);
            st.push(my[k].v);
        }
        while(!st.empty()){
            int now=st.top();st.pop();
            dp[now]=max(dp[now],d[now]);
            d[now]=0;
        }
        i=j-1;
    }
    cout<<*max_element(dp+1,dp+1+n)<<endl;
    return 0;
}