Codeforces Round #677 (Div. 3)——ABCDE解题报告
比赛链接:https://codeforces.com/contest/1433
A.Boring Apartments
题解
直接按照题意模拟整个过程即可。
代码
#include <bits/stdc++.h>
#define PI atan(1.0)*4
#define rp(i,s,t) for (register int i = (s); i <= (t); i++)
#define RP(i,t,s) for (register int i = (t); i >= (s); i--)
#define sc(x) scanf("%d",&x)
#define scl(x) scanf("%lld",&x)
#define ll long long
#define ull unsigned long long
#define mst(a,b) memset(a,b,sizeof(a))
#define lson rt<<1,l,m
#define rson rt<<1|1,m+1,r
#define pii pair<int,int>
#define pll pair<ll,ll>
#define pil pair<int,ll>
#define m_p make_pair
#define p_b push_back
#define ins insert
#define era erase
#define INF 0x3f3f3f3f
#define inf 0x3f3f3f3f3f3f3f3f
#define dg if(debug)
#define pY puts("YES")
#define pN puts("NO")
#define outval(a) cout << "Debuging...|" << #a << ": " << a << "\n";
#define outval2(a,b) cout << "Debuging...|" << #a << ": " << a <<"\t"<< #b << ": " << b << "\n";
#define outval3(a,b,c) cout << "Debuging...|" << #a << ": " << a <<"\t"<< #b << ": " << b <<"\t"<< #c << ": " << c << "\n";
using namespace std;
int debug = 0;
ll gcd(ll a,ll b){
return b?gcd(b,a%b):a;
}
ll lcm(ll a,ll b){
return a/gcd(a,b)*b;
}
inline int read(){
int s=0,f=1;
char ch=getchar();
while(ch<'0'||ch>'9'){
if(ch=='-') f=-1;
ch=getchar();
}
while(ch>='0'&&ch<='9'){
s=s*10+ch-'0';
ch=getchar();
}
return s*f;
}
const int N = 1e5+7;
int a[N];
void solve(){
string s;cin>>s;
string cur="1";
int num=1;
int ans=0;
while(cur!=s){
ans+=cur.size();
if(cur.size()==4){
num++;
cur=(num+'0');
continue;
}
cur+=(num+'0');
// outval2(num,cur);
}
cout<<ans+cur.size()<<endl;
}
int main(){
ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#ifdef ONLINE_JUDGE
#else
freopen("in.txt", "r", stdin);
//debug = 1;
#endif
//time_t beg, end;
//if(debug) beg = clock();
int T;cin>>T;
while(T--) solve();
/*
if(debug) {
end = clock();
printf("time:%.2fs\n", 1.0 * (end - beg) / CLOCKS_PER_SEC);
}
*/
return 0;
}
B.Yet Another Bookshelf
题解
数据比较小,我们可以首先枚举作为中心的连续
1
1
1的串。
然后分为两种情况进行考虑:
1.在中心左边的连续
1
1
1的串
2.在中心右边的连续
1
1
1的串
当该串在中心的左边时,根据贪心的原则从小到大每次把小的连续
1
1
1的串换到第一个比他大的连续的
1
1
1的串的左边最优。
举个例子模拟一下这个过程:
假设串为
1010011010
1010011010
1010011010。
当前作为中心的连续的
1
1
1串为
11
11
11。
把中心左边的连续
1
1
1串交换的步骤如下:
1.
1010011010
−
−
0110011010
1010011010--0110011010
1010011010−−0110011010
2.
0110011010
−
−
0001111010
0110011010--0001111010
0110011010−−0001111010
这样可以保证交换次数最小,中心右边的情况类似,只不过逆序维护。
最后我们会发现,每次枚举中心的答案都是一样的,因此我们就可以直接求出以第一个连续
1
1
1作为中心的最小交换次数即可,至于为什么?可以自己想一想。
代码
#include <bits/stdc++.h>
#define PI atan(1.0)*4
#define rp(i,s,t) for (register int i = (s); i <= (t); i++)
#define RP(i,t,s) for (register int i = (t); i >= (s); i--)
#define sc(x) scanf("%d",&x)
#define scl(x) scanf("%lld",&x)
#define ll long long
#define ull unsigned long long
#define mst(a,b) memset(a,b,sizeof(a))
#define lson rt<<1,l,m
#define rson rt<<1|1,m+1,r
#define pii pair<int,int>
#define pll pair<ll,ll>
#define pil pair<int,ll>
#define m_p make_pair
#define p_b push_back
#define ins insert
#define era erase
#define INF 0x3f3f3f3f
#define inf 0x3f3f3f3f3f3f3f3f
#define dg if(debug)
#define pY puts("YES")
#define pN puts("NO")
#define outval(a) cout << "Debuging...|" << #a << ": " << a << "\n";
#define outval2(a,b) cout << "Debuging...|" << #a << ": " << a <<"\t"<< #b << ": " << b << "\n";
#define outval3(a,b,c) cout << "Debuging...|" << #a << ": " << a <<"\t"<< #b << ": " << b <<"\t"<< #c << ": " << c << "\n";
using namespace std;
int debug = 0;
ll gcd(ll a,ll b){
return b?gcd(b,a%b):a;
}
ll lcm(ll a,ll b){
return a/gcd(a,b)*b;
}
inline int read(){
int s=0,f=1;
char ch=getchar();
while(ch<'0'||ch>'9'){
if(ch=='-') f=-1;
ch=getchar();
}
while(ch>='0'&&ch<='9'){
s=s*10+ch-'0';
ch=getchar();
}
return s*f;
}
const int N = 1e5+7;
int a[N];
struct node{
int l,r;
}p[N];
int tot;
void solve(){
int n=read();
rp(i,1,n) a[i]=read();
tot=0;
rp(i,1,n){
if(!a[i]) continue;
int l=i;
while(i<n&&a[i+1]) i++;
p[++tot]={l,i};
}
int ans=0;
rp(i,1,tot-1) ans+=p[i+1].l-p[i].r-1;
cout<<ans<<endl;
}
int main(){
//ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#ifdef ONLINE_JUDGE
#else
freopen("in.txt", "r", stdin);
//debug = 1;
#endif
//time_t beg, end;
//if(debug) beg = clock();
int T=read();
while(T--) solve();
/*
if(debug) {
end = clock();
printf("time:%.2fs\n", 1.0 * (end - beg) / CLOCKS_PER_SEC);
}
*/
return 0;
}
C.Dominant Piranha
题解
直接暴力枚举开始位置的数,然后模拟整个过程即可。
注意要逆序枚举。
代码
#include <bits/stdc++.h>
#define PI atan(1.0)*4
#define rp(i,s,t) for (register int i = (s); i <= (t); i++)
#define RP(i,t,s) for (register int i = (t); i >= (s); i--)
#define sc(x) scanf("%d",&x)
#define scl(x) scanf("%lld",&x)
#define ll long long
#define ull unsigned long long
#define mst(a,b) memset(a,b,sizeof(a))
#define lson rt<<1,l,m
#define rson rt<<1|1,m+1,r
#define pii pair<int,int>
#define pll pair<ll,ll>
#define pil pair<int,ll>
#define m_p make_pair
#define p_b push_back
#define ins insert
#define era erase
#define INF 0x3f3f3f3f
#define inf 0x3f3f3f3f3f3f3f3f
#define dg if(debug)
#define pY puts("YES")
#define pN puts("NO")
#define outval(a) cout << "Debuging...|" << #a << ": " << a << "\n";
#define outval2(a,b) cout << "Debuging...|" << #a << ": " << a <<"\t"<< #b << ": " << b << "\n";
#define outval3(a,b,c) cout << "Debuging...|" << #a << ": " << a <<"\t"<< #b << ": " << b <<"\t"<< #c << ": " << c << "\n";
using namespace std;
int debug = 0;
ll gcd(ll a,ll b){
return b?gcd(b,a%b):a;
}
ll lcm(ll a,ll b){
return a/gcd(a,b)*b;
}
inline int read(){
int s=0,f=1;
char ch=getchar();
while(ch<'0'||ch>'9'){
if(ch=='-') f=-1;
ch=getchar();
}
while(ch>='0'&&ch<='9'){
s=s*10+ch-'0';
ch=getchar();
}
return s*f;
}
const int N = 3e5+7;
int a[N];
void solve(){
int n=read();
rp(i,1,n) a[i]=read();
a[0]=a[n+1]=INF;
RP(i,n,1){
int f=0;
int cur_num=a[i];
int num=1;
int l=i-1,r=i+1;
while(num<n){
// outval3(cur_num,l,r);
if(a[l]<cur_num) cur_num++,l--,num++;
else if(a[r]<cur_num) cur_num++,r++,num++;
else{
f=1;
break;
}
}
// outval2(i,num);
if(num==n){
cout<<i<<endl;
return ;
}
}
cout<<-1<<endl;
}
int main(){
//ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#ifdef ONLINE_JUDGE
#else
freopen("in.txt", "r", stdin);
//debug = 1;
#endif
//time_t beg, end;
//if(debug) beg = clock();
int T=read();
while(T--) solve();
/*
if(debug) {
end = clock();
printf("time:%.2fs\n", 1.0 * (end - beg) / CLOCKS_PER_SEC);
}
*/
return 0;
}
D.Districts Connection
题解
c
f
cf
cf常规构造题,这个构造不是特别难想。
首先当只有一个类型时肯定不行,输出NO即可。
否则的话,首先输出YES。
然后选择第一个类型的第一个数,和其他不是一个类型的所有数建边,
最后再把第一个类型中(除了第一个数)的所有数和其他(排除了第一个类型)的类型的任意一个数建边即可。
代码
#include <bits/stdc++.h>
#define PI atan(1.0)*4
#define rp(i,s,t) for (register int i = (s); i <= (t); i++)
#define RP(i,t,s) for (register int i = (t); i >= (s); i--)
#define sc(x) scanf("%d",&x)
#define scl(x) scanf("%lld",&x)
#define ll long long
#define ull unsigned long long
#define mst(a,b) memset(a,b,sizeof(a))
#define lson rt<<1,l,m
#define rson rt<<1|1,m+1,r
#define pii pair<int,int>
#define pll pair<ll,ll>
#define pil pair<int,ll>
#define m_p make_pair
#define p_b push_back
#define ins insert
#define era erase
#define INF 0x3f3f3f3f
#define inf 0x3f3f3f3f3f3f3f3f
#define dg if(debug)
#define pY puts("YES")
#define pN puts("NO")
#define outval(a) cout << "Debuging...|" << #a << ": " << a << "\n";
#define outval2(a,b) cout << "Debuging...|" << #a << ": " << a <<"\t"<< #b << ": " << b << "\n";
#define outval3(a,b,c) cout << "Debuging...|" << #a << ": " << a <<"\t"<< #b << ": " << b <<"\t"<< #c << ": " << c << "\n";
using namespace std;
int debug = 0;
ll gcd(ll a,ll b){
return b?gcd(b,a%b):a;
}
ll lcm(ll a,ll b){
return a/gcd(a,b)*b;
}
inline int read(){
int s=0,f=1;
char ch=getchar();
while(ch<'0'||ch>'9'){
if(ch=='-') f=-1;
ch=getchar();
}
while(ch>='0'&&ch<='9'){
s=s*10+ch-'0';
ch=getchar();
}
return s*f;
}
const int N = 5e3+7;
int a[N];
vector<int> v[N];
vector<int> data;
void init() { data.clear(); }
void Insert(int val) { data.push_back(val); }
void doit() {
sort(data.begin(), data.end());
data.erase(unique(data.begin(), data.end()), data.end());
}
int g(int val) { return lower_bound(data.begin(), data.end(), val) - data.begin() + 1; }
void solve(){
int n=read();
init();
rp(i,1,n) a[i]=read(),Insert(a[i]);
doit();
int len=data.size();
if(len==1){
pN;
return ;
}
pY;
rp(i,1,n) a[i]=g(a[i]);
rp(i,1,n) v[i].clear();
rp(i,1,n) v[a[i]].push_back(i);
// rp(i,1,len){
// cout<<i<<endl;
// for(auto val:v[i]) cout<<val<<" ";
// cout<<endl;
// }
int cnt=0;
int cur=v[1][0];
rp(i,2,len){
cnt+=v[i].size();
for(auto val:v[i]) cout<<cur<<" "<<val<<endl;
}
rp(i,1,v[1].size()-1){
cnt++;
cout<<v[1][i]<<" "<<v[2][0]<<endl;
}
}
int main(){
//ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#ifdef ONLINE_JUDGE
#else
freopen("in.txt", "r", stdin);
//debug = 1;
#endif
//time_t beg, end;
//if(debug) beg = clock();
int T=read();
while(T--) solve();
/*
if(debug) {
end = clock();
printf("time:%.2fs\n", 1.0 * (end - beg) / CLOCKS_PER_SEC);
}
*/
return 0;
}
E.Two Round Dances
题解
数学组合计数题,首先考虑选取两轮舞蹈的所有方案数
u
p
up
up。
不难得到
u
p
=
C
n
n
2
×
A
n
2
n
2
×
C
n
2
n
2
×
A
n
2
n
2
up=C_{n}^{\frac{n}{2}}\times A_{\frac{n}{2}}^{\frac{n}{2}}\times C_{\frac{n}{2}}^{\frac{n}{2}}\times A_{\frac{n}{2}}^{\frac{n}{2}}
up=Cn2n×A2n2n×C2n2n×A2n2n。
然后我需要考虑重复的个数
d
o
w
n
down
down,手推2,4,6,8的情况可以得到
d
o
w
n
=
(
n
2
)
×
(
n
2
)
×
2
down=(\frac{n}{2})\times (\frac{n}{2}) \times 2
down=(2n)×(2n)×2。
最终答案就是所有方案数除以重复个数(即
u
p
d
o
w
n
\frac{up}{down}
downup)。
代码
#include <bits/stdc++.h>
#define PI atan(1.0)*4
#define rp(i,s,t) for (register int i = (s); i <= (t); i++)
#define RP(i,t,s) for (register int i = (t); i >= (s); i--)
#define sc(x) scanf("%d",&x)
#define scl(x) scanf("%lld",&x)
#define ll unsigned long long
#define mst(a,b) memset(a,b,sizeof(a))
#define lson rt<<1,l,m
#define rson rt<<1|1,m+1,r
#define pii pair<int,int>
#define pll pair<ll,ll>
#define pil pair<int,ll>
#define m_p make_pair
#define p_b push_back
#define ins insert
#define era erase
#define INF 0x3f3f3f3f
#define inf 0x3f3f3f3f3f3f3f3f
#define dg if(debug)
#define pY puts("YES")
#define pN puts("NO")
#define outval(a) cout << "Debuging...|" << #a << ": " << a << "\n";
#define outval2(a,b) cout << "Debuging...|" << #a << ": " << a <<"\t"<< #b << ": " << b << "\n";
#define outval3(a,b,c) cout << "Debuging...|" << #a << ": " << a <<"\t"<< #b << ": " << b <<"\t"<< #c << ": " << c << "\n";
using namespace std;
int debug = 0;
ll gcd(ll a,ll b){
return b?gcd(b,a%b):a;
}
ll lcm(ll a,ll b){
return a/gcd(a,b)*b;
}
inline int read(){
int s=0,f=1;
char ch=getchar();
while(ch<'0'||ch>'9'){
if(ch=='-') f=-1;
ch=getchar();
}
while(ch>='0'&&ch<='9'){
s=s*10+ch-'0';
ch=getchar();
}
return s*f;
}
const int N = 1e5+7;
ll fac[N];
ll C(int n,int m){
return fac[n]/(fac[n-m]*fac[m]);
}
ll A(int n,int m){
return fac[n]/fac[n-m];
}
void solve(){
int n=read();
fac[0]=1;
rp(i,1,n) fac[i]=(fac[i-1]*i);
cout<<C(n,n/2)*A(n/2,n/2)*A(n/2,n/2)/((1ll*n*n)/2)<<endl;
}
int main(){
//ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#ifdef ONLINE_JUDGE
#else
freopen("in.txt", "r", stdin);
//debug = 1;
#endif
//time_t beg, end;
//if(debug) beg = clock();
int T=1;
while(T--) solve();
/*
if(debug) {
end = clock();
printf("time:%.2fs\n", 1.0 * (end - beg) / CLOCKS_PER_SEC);
}
*/
return 0;
}