- layout: post
- title: Codeforces Round 261(Div. 2)
- author: "luowentaoaa"
- catalog: true
- tags:
- mathjax: true
- - codeforces
- - dp
传送门 https://codeforces.com/contest/459
A - Pashmak and Garden https://codeforces.com/contest/459/problem/A (签到)
题意
对于一个正方形给你其中两个点, 让你输出另外两个点
思路
水
- #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 https://codeforces.com/contest/459/problem/B (水题)
题意
一堆数, 找出两个数使得差值最大, 输出这两个数有多少种选择
- #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 https://codeforces.com/contest/459/problem/C (dfs 暴力)
题意
n 个人 m 天 k 个车每个人每天都要坐车, 要不能出现任意两个人 m 天做的车都一样
思路
相当于不能有两个长度为 m 的字符串完全相同
- #include
- #include
- #include
- #include
- #include
- 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 https://codeforces.com/contest/459/problem/D (树状数组)
题意
定义
\[ f(l,r,x)= 区间 [l,r] 中值等于 x 的个数 \]
求有多少对
\[ f(1,i,ai)>f(j,n,aj) \]
思路
直接维护从后向前的值, 然后从前往后遍历 查找后面小于它的值
树状数组维护
- #include
- #include
- #include
- #include
- #include
- #include
- 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 https://codeforces.com/contest/459/problem/E (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++;
- stackst;
- 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;
- }
来源: http://www.bubuko.com/infodetail-2980175.html