生活随笔
收集整理的這篇文章主要介紹了
Codeforces Global Round 11 ABCD题解
小編覺得挺不錯的,現在分享給大家,幫大家做個參考.
真陰間啊 ， 不僅時長陰間， 題目也有點emmmmm
打的不順利，沒有按預想在15分鐘內把AB題寫出來 ((｡･?･)ﾉﾞ害)
開局碼了發A WA2 人傻了 開始質疑自己了 先擱著吧
然后又碼了一個半成品B emmm 有bug 又鴿著了
然后C好像沒啥想法 鴿著 看看D
如果沒有翻譯我估計D題我是寫不出來的 QAQ 簡直閱讀理解
1427A題鏈接
給你一個數組 要我們重新排列以后 對于任意長度的前綴和不為0
那么考慮長度為n的前綴和 ，如果它為0 那么必然不可行 輸出NO
否則根據前綴和的大小 考慮是從大到小輸出 還是從小到大輸出
非常簡單 (然后我當時不知道在討論啥玩意 WA2)
#include<bits/stdc++.h>
#include<stdlib.h>
#include<algorithm>
#include<stdio.h>
#include<string.h>
#include<queue>
#include<time.h>
#include <cstdio>
#include <iostream>
#include <vector>
#define ll long long
#define int long long
#define inf 0x3f3f3f3f
#define mods 1000000007
#define modd 998244353
#define PI acos(-1)
#define fi first
#define se second
#define lowbit(x) (x&(-x))
#define mp make_pair
#define pb push_back
#define si size()
#define E exp(1.0)
#define fixed cout.setf(ios::fixed)
#define fixeds(x) setprecision(x)
#define IOS ios::sync_with_stdio(false);cin.tie(0)using namespace std
;ll
gcd(ll a
,ll b
){if(a
<0)a
=-a
;if(b
<0)b
=-b
;return b
==0?a
:gcd(b
,a
%b
);}
template<typename T
>void read(T
&res
){bool flag
=false;char ch
;while(!isdigit(ch
=getchar()))(ch
=='-')&&(flag
=true);
for(res
=ch
-48;isdigit(ch
=getchar());res
=(res
<<1)+(res
<<3)+ch
- 48);flag
&&(res
=-res
);}
ll
lcm(ll a
,ll b
){return a
*b
/gcd(a
,b
);}
ll
qp(ll a
,ll b
,ll mod
){ll ans
=1;if(b
==0){return ans
%mod
;}while(b
){if(b
%2==1){b
--;ans
=ans
*a
%mod
;}a
=a
*a
%mod
;b
=b
/2;}return ans
%mod
;}
ll
qpn(ll a
,ll b
, ll p
){ll ans
= 1;a
%=p
;while(b
){if(b
&1){ans
= (ans
*a
)%p
;--b
;}a
=(a
*a
)%p
;b
>>= 1;}return ans
%p
;}const int ma
=1;
ll a
[200];
ll b
[200];
signed main(){
ll t
;
read(t
);
while(t
--){
ll n
;
read(n
);
ll la
=0;
ll lb
=0;
ll add
=0;
ll f
=0;
for(int i
=1;i
<=n
;i
++){
read(a
[i
]);
add
=add
+a
[i
];}
if(add
==0){printf("NO\n");continue;
}sort(a
+1,a
+1+n
);if(add
>0){printf("YES\n");for(int i
=n
;i
>=1;i
--){printf("%lld ",a
[i
]);}}else{printf("YES\n");for(int i
=1;i
<=n
;i
++){printf("%lld ",a
[i
]);}}
printf("\n");
}
}
1427B鏈接
給一個長度為n的字符串 包含L W代表輸贏
輸了沒有積分， 單贏拿一分，連續贏(前一個是W 后一個也是W) 拿兩分
給了我們操作數 K 可以更改 字符串 詢問最終可以拿最多 多少分
觀察一下WLW WLLW LLW WLL
不難不發 如果能填充W之間的縫隙 顯然貢獻值是最高的
那么我們要分類處理
先找到第一個W的pos 和最后一個W的pos 在這個區間里面找長度L的縫隙 存起來 排序 優先填充小的
如果處理完了以后還有多的K 可以使用 那么就處理1-- <pos1 以及 pos2+1 到n
思路就這樣 碼起來有點點麻煩
https
://paste
.ubuntu
.com
/p
/v2m3FzCHFQ
/ 鏈接里面
1247C
感覺挺像寒假訓練營那個寶可夢的問題
題目給了我們一個R長度的坐標系
自己初始位置為(1, 1)
現在有n個人 在不同時間出現在不同的地點 時間過了會消失
移動速度是1s 一個單位 問最多能遇到多少個人
（說到這一步就看自己有沒有寒假好好補題了）
#include<bits/stdc++.h>
#include<stdlib.h>
#include<algorithm>
#include<stdio.h>
#include<string.h>
#include<queue>
#include<time.h>
#include <cstdio>
#include <iostream>
#include <vector>
#define ll long long
#define int long long
#define inf 0x3f3f3f3f
#define mods 1000000007
#define modd 998244353
#define PI acos(-1)
#define fi first
#define se second
#define lowbit(x) (x&(-x))
#define mp make_pair
#define pb push_back
#define si size()
#define E exp(1.0)
#define fixed cout.setf(ios::fixed)
#define fixeds(x) setprecision(x)
#define IOS ios::sync_with_stdio(false);cin.tie(0)
using namespace std
;
ll
gcd(ll a
,ll b
)
{if(a
<0)a
=-a
;if(b
<0)b
=-b
;return b
==0?a
:gcd(b
,a
%b
);
}
template<typename T
>void read(T
&res
)
{bool flag
=false;char ch
;while(!isdigit(ch
=getchar()))(ch
=='-')&&(flag
=true);for(res
=ch
-48; isdigit(ch
=getchar()); res
=(res
<<1)+(res
<<3)+ch
- 48);flag
&&(res
=-res
);
}
ll
lcm(ll a
,ll b
)
{return a
*b
/gcd(a
,b
);
}
ll
qp(ll a
,ll b
,ll mod
)
{ll ans
=1; if(b
==0){return ans
%mod
;}while(b
){if(b
%2==1){b
--;ans
=ans
*a
%mod
;}a
=a
*a
%mod
;b
=b
/2;}return ans
%mod
;
}
ll
qpn(ll a
,ll b
, ll p
)
{ll ans
= 1; a
%=p
;while(b
){if(b
&1){ans
= (ans
*a
)%p
;--b
;}a
=(a
*a
)%p
;b
>>= 1;}return ans
%p
;
}
const int maxn
=1e6+7;
int euler
[maxn
],prime
[maxn
],cntt
;
void Euler(int n
)
{memset(euler
,0,sizeof(euler
));euler
[1]=0;cntt
=0;for(int i
=2; i
<=n
; i
++){if(!euler
[i
]){euler
[i
]=i
-1;prime
[cntt
++]=i
;}for(int j
=0; j
<cntt
&&prime
[j
]*i
<=n
; j
++){if(i
%prime
[j
])euler
[prime
[j
]*i
]=euler
[i
]*(prime
[j
]-1);else{euler
[prime
[j
]*i
]=euler
[i
]*prime
[j
];break;}}}
}struct pe
{
ll t
;
ll x
;
ll y
;}sb
[1000006];
const int op
=1e6+7;
ll pre
[op
],dp
[op
];
ll fac
[op
];
ll dp2
[op
];
bool check(ll i
,ll j
){if(abs(sb
[i
].x
-sb
[j
].x
)+abs(sb
[i
].y
-sb
[j
].y
)<=(sb
[i
].t
-sb
[j
].t
)){return true;}
return false;
}
signed main()
{ fac
[1]=1;ll n
,r
;read(r
);read(n
);for(int i
=1;i
<=n
;i
++){read(sb
[i
].t
);read(sb
[i
].x
);read(sb
[i
].y
);}sb
[0].t
=0;sb
[0].x
=1;sb
[0].y
=1;for(int i
=0;i
<=n
;i
++){pre
[i
]=-inf
;dp
[i
]=-inf
;}dp
[0]=0;pre
[0]=0;ll need
=0;for(int i
=1;i
<=n
;i
++){if(i
>1000) dp
[i
]=pre
[i
-1001]+1;for(int j
=max(need
,i
-1002);j
<i
;j
++){if(check(i
,j
)){dp
[i
]=max(dp
[i
],dp
[j
]+1);}else{continue;}}pre
[i
]=max(pre
[i
-1],dp
[i
]);}ll ans
=0;ll ma
=0;for(int i
=1;i
<=n
;i
++) {ans
=max(ans
,dp
[i
]);}printf("%lld\n",ans
);return 0;
}
1427D鏈接
給我們一個序列 我們可以把它劃分為若干個塊 從左往右
然后塊D_k D_(k-1) ----- D1 逆排列 但是塊里面的順序不變
問操作多少次可以使得序列變得有序 1–n排列
輸出操作次數以及 每次的劃分塊數 和劃分每個塊的大小
注意到n很小 而且題目也不要求極限化操作次數
那么直接暴力劃分就好了， 最壞的情況下一次劃分 只能使得一個數歸位
52次而已 暴力足以
舉個栗子 6 5 4 3 2 1 劃分1 1 4 變為 4 3 2 1 5 6
劃分1 1 4 變為 2 1 5 6 3 4
劃分1 1 4 變為 5 6 3 4 1 2
劃分 2 2 2 變為 1 2 3 4 5 6
#include<bits/stdc++.h>
#include<stdlib.h>
#include<algorithm>
#include<stdio.h>
#include<string.h>
#include<queue>
#include<time.h>
#include <cstdio>
#include <iostream>
#include <vector>
#define ll long long
#define int long long
#define inf 0x3f3f3f3f
#define mods 1000000007
#define modd 998244353
#define PI acos(-1)
#define fi first
#define se second
#define lowbit(x) (x&(-x))
#define mp make_pair
#define pb push_back
#define si size()
#define E exp(1.0)
#define fixed cout.setf(ios::fixed)
#define fixeds(x) setprecision(x)
#define IOS ios::sync_with_stdio(false);cin.tie(0)
using namespace std
;
ll
gcd(ll a
,ll b
)
{if(a
<0)a
=-a
;if(b
<0)b
=-b
;return b
==0?a
:gcd(b
,a
%b
);
}
template<typename T
>void read(T
&res
)
{bool flag
=false;char ch
;while(!isdigit(ch
=getchar()))(ch
=='-')&&(flag
=true);for(res
=ch
-48; isdigit(ch
=getchar()); res
=(res
<<1)+(res
<<3)+ch
- 48);flag
&&(res
=-res
);
}
ll
lcm(ll a
,ll b
)
{return a
*b
/gcd(a
,b
);
}
ll
qp(ll a
,ll b
,ll mod
)
{ll ans
=1; if(b
==0){return ans
%mod
;}while(b
){if(b
%2==1){b
--;ans
=ans
*a
%mod
;}a
=a
*a
%mod
;b
=b
/2;}return ans
%mod
;
}
ll
qpn(ll a
,ll b
, ll p
)
{ll ans
= 1; a
%=p
;while(b
){if(b
&1){ans
= (ans
*a
)%p
;--b
;}a
=(a
*a
)%p
;b
>>= 1;}return ans
%p
;
}
vector
<int> v
[100009];
ll a
[609];
ll b
[609];
vector
<int> ans
[100009];
signed main()
{ll n
;read(n
);ll sum
=0;ll rnm
=0;for(int i
=1; i
<=n
; i
++){read(a
[i
]);if(a
[i
]>a
[i
-1]){rnm
++;}}ll ti
=0;while(true){ti
++;ll cnt
=1,p1
,p
;bool flag
=0;for(int i
=2; i
<=n
; i
++){if(a
[i
-1]!=a
[i
]-1){flag
=1;}else{continue;}}if(!flag
)break;for(int i
=1; i
<=n
; i
++){if(a
[i
]!=i
){p1
=i
;break;}else{continue;}}if(p1
!=1){ans
[ti
].pb(p1
-1);}else{sum
++;}for(int i
=p1
+1; i
<=n
; i
++){if(a
[i
-1]==a
[i
]-1){cnt
++;continue;}if(a
[i
-1]!=a
[i
]-1){p
=a
[p1
];p
++;p
--;p1
=i
;break;}}ans
[ti
].pb(cnt
);cnt
=1;for(int i
=p1
; i
<=n
; i
++){if(a
[i
]==p
-1){p1
=i
;ans
[ti
].pb(cnt
);break;}cnt
++;}if(p1
!=n
)ans
[ti
].pb(n
-p1
);int pos
=n
,now
=1;for(int i
=ans
[ti
].size()-1; i
>=0; i
--){for(int j
=pos
-ans
[ti
][i
]+1; j
<=pos
; j
++){b
[now
++]=a
[j
];}pos
=pos
-ans
[ti
][i
];}for(int i
=1; i
<=n
; i
++){a
[i
]=b
[i
];}}printf("%lld\n",ti
-1);for(int i
=1; i
<ti
; i
++){printf("%lld ",ans
[i
].size());for(int j
=0; j
<ans
[i
].size(); j
++){printf("%lld ",ans
[i
][j
]);}printf("\n");}return 0;}
E題不會 但是應該可以補 qwq
開局預測-174 結束的時候上到2000分了 就很刺激
總結
以上是生活随笔為你收集整理的Codeforces Global Round 11 ABCD题解的全部內容，希望文章能夠幫你解決所遇到的問題。
如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。
