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;
}