【补题日记】CF#744 Div.3 & 2020 ICPC沈阳站

Pro

Codeforces Round #744 (Div. 3)

The 2020 ICPC Asia Shenyang Regional Programming Contest

补题，不会写所有题目题解，请看清problem name

Sol

C. Ticks

比赛的时候忘记看这个题了 枚举题，枚举每一个$\ast$，去看这个$\ast$是否能组成“边长”大于等于k的两条边。

如果可以就给路过的所有$\ast$打上标记，最后是否所有的$\ast$均有标记就可以判断是否可以了。

D. Productive Meeting

开始的时候想到了第一大和第二大在一起贪心最好，但是仅仅比较了初始的最大和次大。

即，本题正确的贪心策略为：每次都是最大和次大交谈最好。贪心策略没想完整。

E2. Array Optimization by Deque

本题比E1仅仅多了求逆序对，这里我写的树状数组求逆序对。

所以每次直接往树状数组中值的位置加1就可以，然后判断应该放到前面还是后面。

如果放到前面，对应的是求$1\sim a[i-1]$的和；

如果放到后面，对应的是求$1\sim m$（m为输入数据最大值）的和与$1\sim a[i]$的和，二者的差值。

然后以上二者求一个min，累加即为答案。

F. Array Stabilization (AND version)

因为是与运算，所以0参与与运算才可以让答案变为0，所以存下0的位置。

然后模拟移动的过程，如果新产生的结果仍为0，则再重复上述过程。

最后判断该数组是否全部为0。

D. Journey to Un’Goro

搜索加剪枝，但是还是挺考思维的。

先看第一问，全部都是r的时候的结果一定最大，只需要求出全部是r的时候的答案就可以。

将b考虑为0，r考虑为1。则本题求r为奇数时的情况，即区间异或和不为0。

设$a_i$表示长度为$i$时，r的个数，则区间(i,j)内r的个数为$a_j-a_{i-1}$

所以，当$a_j$与$a_{i-1}$的奇偶性不同时，r的个数为奇数。

注意，这里的$a_0$可以取到，因为如果不取那么第一个位置就算不进去了。

这里$a_0$的意义是前缀为空，r的个数为0。

容易想到，当全部为r时产生的结果一定最大，所以考虑全部为r时的答案。

此时一共有n+1种取法（因为有$a_0$），所以根据$a+b=m,a\times b\le \lfloor \frac{m}{2}\rfloor \lceil \frac{m}{2}\rceil$，因此第一问答案为：$\lfloor \frac{n+1}{2}\rfloor \lceil \frac{n+1}{2}\rceil$

注意要开long long！！！

第二问，因为只要输出100个，所以搜索的复杂度可以接受。

这里我没用异或，因为我感觉直接判断会更加直观。

因为只有r才会改变奇偶性，又因为要考虑字典序，所以先考虑b的情况。

当放入b的时候，因为b不会改变奇偶性，所以放入b的时候直接在cnt0(cnt1)的位置加1。

当放入r的时候，r会改变奇偶性，所以放入r的时候，之前是奇数时，应在偶数位置加1，偶数同理。

一个剪枝：由第一问答案可以知道，奇数和偶数的个数一定小于$\lceil \frac{n+1}{2}\rceil$，一旦有大于这个数字的，直接返回。

之后能搜到最后的，一定就是满足的字符串。

F. Kobolds and Catacombs

把每一个数字应该在的位置求出来，现在位置和应该在的位置之间的数一定在一个区间内。

而这个区间还可以更大，所以就枚举这个区间内每一个数字，找应该在的位置的最大值。

而此时，如果最大值与当前区间的右端点不重合时，说明区间至少还可以扩展到位置的最大值。

而不可以直接跳过去，因为当前区间的右端点和位置最大值之间仍有一段区间。

枚举这段区间中应该在的位置的最大值，重复上述扩展的过程，直到右端点是区间内应该在的位置的最大值。

G. The Witchwood

数组前K大，注意开long long

K. Scholomance Academy

容易想到，$\theta$的取值只需要在输入的n个数中枚举即可，又容易发现随着$\theta$从大到小的变化，FPR也呈单调变化。

具体而言，随着$\theta$从大到小变化，如果actual为正，FN减1，TP加1；如果actual为负，TN减1，FP加1。

FPR是逐渐增大的，TPR是可以求出来的，所以临时存下来上一个FPR的值，两个FPR之间的差值为横坐标。

O(1)可以求的TPR的值，二者相乘累加即为答案。

需要注意一点：排序的时候如果输入的数字相等，仅仅正负号不同怎么办？

应该先算负号，因为本题中正号仅会使纵坐标发生变化，负号仅会使横坐标发生变化。

所以当遇到一个新的值（这个值有一正一负的actual），应该用一个负号来求出上一部分的答案，

而非用一个正号继续提高纵坐标的值。

也就是说，每一个负号是每个数字的分界点，当上一个值算完后，应该先算一个负号再开启一个新的值。

Code

C. Ticks

//By cls1277
#include<iostream>
#include<cstdio>
#include<queue>
#include<cstring>
#include<string>
#include<algorithm>
#include<cmath>
#include<vector>
#include<map>
#include<stack>
#include<sstream>
#include<set>
#include<cassert>
#include<bitset>
using namespace std;
typedef long long LL;
#define PI acos(-1)
#define INF 2147483647
#define eps 1e-7
#define Fo(i,a,b) for(LL i=(a); i<=(b); i++)
#define Ro(i,b,a) for(LL i=(b); i>=(a); i--)
#define Eo(i,x,_) for(LL i=head[x]; i; i=_[i].next)
#define Ms(a,b) memset((a),(b),sizeof(a))
#define lowbit(_) _&(-_)
#define ls x<<1
#define rs x<<1|1
#define endl 'n'
inline LL read() {
LL x = 0, f = 1;char c = getchar();
while (!isdigit(c)) { if (c == '-')f = -f;c = getchar(); }
while (isdigit(c)) x = (x << 1) + (x << 3) + (c ^ 48ll), c = getchar();
return x * f;
}
const LL maxn = 25;
int T , n , m , k;
char mp[maxn][maxn];
vector<pair<int,int>>a;
bool b[maxn][maxn];
int main() {
ios::sync_with_stdio(false);
#ifdef DEBUG
freopen("data.txt","r",stdin);
#endif
cin>>T;
while(T--) {
cin>>n>>m>>k;
Ms(b,0); a.clear();
Fo(i,1,n)
Fo(j,1,m) {
cin>>mp[i][j];
if(mp[i][j]=='*') a.push_back(make_pair(i,j));
}
for(int i=0; i<a.size(); i++) {
int ux=a[i].first , uy=a[i].second;
if(ux-k<=0||uy-k<=0||uy+k>m) continue;
int cnt=1;
while(mp[ux-cnt][uy-cnt]=='*'&&mp[ux-cnt][uy+cnt]=='*')
cnt++;
cnt--;
if(cnt>=k) {
b[ux][uy] = 1;
while(cnt) b[ux-cnt][uy-cnt]=b[ux-cnt][uy+cnt]=1,cnt--;
}
}
int flag = 0;
for(int i=0; i<a.size(); i++)
if(b[a[i].first][a[i].second]==0) {
flag = 1;
break;
}
if(flag) cout<<"NO"<<endl;
else cout<<"YES"<<endl;
}
return 0;
}

D. Productive Meeting

//By cls1277
#include<iostream>
#include<cstdio>
#include<queue>
#include<cstring>
#include<string>
#include<algorithm>
#include<cmath>
#include<vector>
#include<map>
#include<stack>
#include<sstream>
#include<set>
#include<cassert>
#include<bitset>
using namespace std;
typedef long long LL;
#define PI acos(-1)
#define INF 2147483647
#define eps 1e-7
#define Fo(i,a,b) for(LL i=(a); i<=(b); i++)
#define Ro(i,b,a) for(LL i=(b); i>=(a); i--)
#define Eo(i,x,_) for(LL i=head[x]; i; i=_[i].next)
#define Ms(a,b) memset((a),(b),sizeof(a))
#define lowbit(_) _&(-_)
#define ls x<<1
#define rs x<<1|1
#define endl 'n'
inline LL read() {
LL x = 0, f = 1;char c = getchar();
while (!isdigit(c)) { if (c == '-')f = -f;c = getchar(); }
while (isdigit(c)) x = (x << 1) + (x << 3) + (c ^ 48ll), c = getchar();
return x * f;
}
const LL maxn = 1e5+5;
int T , n , tot;
pair<int,int>ans[maxn];
priority_queue<pair<int,int>>q;
int main() {
ios::sync_with_stdio(false);
#ifdef DEBUG
freopen("data.txt","r",stdin);
#endif
cin>>T;
while(T--) {
cin>>n; tot=0;
while(!q.empty()) q.pop();
Fo(i,1,n) {
int x; cin>>x;
if(x) q.push(make_pair(x,i));
}
while(q.size()>1) {
pair<int,int> u=q.top(); q.pop();
pair<int,int> v=q.top(); q.pop();
ans[++tot] = make_pair(u.second,v.second);
v.first--; u.first--;
if(v.first) q.push(v);
if(u.first) q.push(u);
}
cout<<tot<<endl;
Fo(i,1,tot) cout<<ans[i].first<<" "<<ans[i].second<<endl;
}
return 0;
}

E2. Array Optimization by Deque

//By cls1277
#include<iostream>
#include<cstdio>
#include<queue>
#include<cstring>
#include<string>
#include<algorithm>
#include<cmath>
#include<vector>
#include<map>
#include<stack>
#include<sstream>
#include<set>
#include<cassert>
#include<bitset>
using namespace std;
typedef long long LL;
#define PI acos(-1)
#define INF 2147483647
#define eps 1e-7
#define Fo(i,a,b) for(LL i=(a); i<=(b); i++)
#define Ro(i,b,a) for(LL i=(b); i>=(a); i--)
#define Eo(i,x,_) for(LL i=head[x]; i; i=_[i].next)
#define Ms(a,b) memset((a),(b),sizeof(a))
#define lowbit(_) _&(-_)
#define ls x<<1
#define rs x<<1|1
#define endl 'n'
inline LL read() {
LL x = 0, f = 1;char c = getchar();
while (!isdigit(c)) { if (c == '-')f = -f;c = getchar(); }
while (isdigit(c)) x = (x << 1) + (x << 3) + (c ^ 48ll), c = getchar();
return x * f;
}
const LL maxn = 2e5+5;
LL T , n , m , a[maxn] , b[maxn] , ans;
struct BIT {
LL tree[maxn];
void add(LL x , LL y) {
while(x<=n) {
tree[x]+=y;
x+=lowbit(x);
}
return ;
}
LL sum(LL x) {
LL res=0;
while(x) {
res+=tree[x];
x-=lowbit(x);
}
return res;
}
}cls;
int main() {
ios::sync_with_stdio(false);
#ifdef DEBUG
freopen("data.txt","r",stdin);
#endif
cin>>T;
while(T--) {
cin>>n;
Ms(cls.tree,0); ans=0;
Fo(i,1,n) {
cin>>a[i];
b[i] = a[i];
}
sort(b+1,b+n+1);
m=unique(b+1,b+n+1)-b-1;
Fo(i,1,n)
a[i]=lower_bound(b+1,b+m+1,a[i])-b;
Fo(i,1,n) {
cls.add(a[i],1);
ans+=min(cls.sum(a[i]-1),cls.sum(m)-cls.sum(a[i]));
}
cout<<ans<<endl;
}
return 0;
}

F. Array Stabilization (AND version)

//By cls1277
#include<iostream>
#include<cstdio>
#include<queue>
#include<cstring>
#include<string>
#include<algorithm>
#include<cmath>
#include<vector>
#include<map>
#include<stack>
#include<sstream>
#include<set>
#include<cassert>
#include<bitset>
using namespace std;
typedef long long LL;
#define PI acos(-1)
#define INF 2147483647
#define eps 1e-7
#define Fo(i,a,b) for(LL i=(a); i<=(b); i++)
#define Ro(i,b,a) for(LL i=(b); i>=(a); i--)
#define Eo(i,x,_) for(LL i=head[x]; i; i=_[i].next)
#define Ms(a,b) memset((a),(b),sizeof(a))
#define lowbit(_) _&(-_)
#define ls x<<1
#define rs x<<1|1
#define endl 'n'
inline LL read() {
LL x = 0, f = 1;char c = getchar();
while (!isdigit(c)) { if (c == '-')f = -f;c = getchar(); }
while (isdigit(c)) x = (x << 1) + (x << 3) + (c ^ 48ll), c = getchar();
return x * f;
}
const LL maxn = 1e6+5;
int T , n , a[maxn] , d , ans;
queue<pair<int,int>>q;
int main() {
ios::sync_with_stdio(false);
#ifdef DEBUG
freopen("data.txt","r",stdin);
#endif
cin>>T;
while(T--) {
ans=0;
cin>>n>>d; int flag=0;
Fo(i,0,n-1) cin>>a[i];
Fo(i,0,n-1) if(!a[i]) q.push(make_pair(0,i));
while(!q.empty()) {
pair<int,int>u=q.front(); q.pop();
int ops = (u.second+d)%n;
if(a[ops]) {
a[ops]=0;
q.push(make_pair(u.first+1,ops));
ans = max(ans,u.first+1);
}
}
Fo(i,0,n-1) if(a[i]) {
flag = 1;
break;
}
if(flag) cout<<"-1"<<endl;
else cout<<ans<<endl;
}
return 0;
}

D. Journey to Un’Goro

//By cls1277
#include<iostream>
#include<cstdio>
#include<queue>
#include<cstring>
#include<string>
#include<algorithm>
#include<cmath>
#include<vector>
#include<map>
#include<stack>
#include<sstream>
#include<set>
#include<cassert>
#include<bitset>
using namespace std;
typedef long long LL;
#define PI acos(-1)
#define INF 2147483647
#define eps 1e-7
#define Fo(i,a,b) for(LL i=(a); i<=(b); i++)
#define Ro(i,b,a) for(LL i=(b); i>=(a); i--)
#define Eo(i,x,_) for(LL i=head[x]; i; i=_[i].next)
#define Ms(a,b) memset((a),(b),sizeof(a))
#define lowbit(_) _&(-_)
#define mk(_,__) make_pair(_,__)
#define pii pair<int,int>
#define ls x<<1
#define rs x<<1|1
#define endl 'n'
inline LL read() {
LL x = 0, f = 1;char c = getchar();
while (!isdigit(c)) { if (c == '-')f = -f;c = getchar(); }
while (isdigit(c)) x = (x << 1) + (x << 3) + (c ^ 48ll), c = getchar();
return x * f;
}
const LL maxn = 1e5+5;
int n , cnt;
char s[maxn];
void dfs(int x , int cnt0, int cnt1 , int z) {
if(cnt0>(n+2)/2||cnt1>(n+2)/2) return ;
if(x==n) {
cout<<s<<endl;
if(++cnt>=100)
exit(0);
return ;
}
s[x]='b';
if(!z) dfs(x+1,cnt0+1,cnt1,0);
else dfs(x+1,cnt0,cnt1+1,1);
s[x]='r';
if(!z) dfs(x+1,cnt0,cnt1+1,1);
else dfs(x+1,cnt0+1,cnt1,0);
return ;
}
int main() {
ios::sync_with_stdio(false);
#ifdef DEBUG
freopen("data.txt","r",stdin);
#endif
cin>>n;
cout<<1LL*((n+1)/2)*((n+2)/2)<<endl;
dfs(0,1,0,0);
return 0;
}

F. Kobolds and Catacombs

//By cls1277
#include<iostream>
#include<cstdio>
#include<queue>
#include<cstring>
#include<string>
#include<algorithm>
#include<cmath>
#include<vector>
#include<map>
#include<stack>
#include<sstream>
#include<set>
#include<cassert>
#include<bitset>
using namespace std;
typedef long long LL;
#define PI acos(-1)
#define INF 2147483647
#define eps 1e-7
#define Fo(i,a,b) for(LL i=(a); i<=(b); i++)
#define Ro(i,b,a) for(LL i=(b); i>=(a); i--)
#define Eo(i,x,_) for(LL i=head[x]; i; i=_[i].next)
#define Ms(a,b) memset((a),(b),sizeof(a))
#define lowbit(_) _&(-_)
#define mk(_,__) make_pair(_,__)
#define pii pair<int,int>
#define ls x<<1
#define rs x<<1|1
#define endl 'n'
inline LL read() {
LL x = 0, f = 1;char c = getchar();
while (!isdigit(c)) { if (c == '-')f = -f;c = getchar(); }
while (isdigit(c)) x = (x << 1) + (x << 3) + (c ^ 48ll), c = getchar();
return x * f;
}
const LL maxn = 1e6+5;
int n , a[maxn] , c[maxn] , ans;
pii b[maxn];
int main() {
ios::sync_with_stdio(false);
#ifdef DEBUG
freopen("data.txt","r",stdin);
#endif
cin>>n;
Fo(i,1,n) {
cin>>a[i];
b[i] = mk(a[i],i);
}
sort(b+1,b+n+1);
Fo(i,1,n) c[b[i].second]=i;
//Fo(i,1,n) cout<<c[i]<<" ";
Fo(i,1,n) {
int r=c[i] , y;
do {
y=r;
Fo(j,i,y) r=max(r,c[j]);
}while(r!=y);
i=r;
ans++;
}
cout<<ans;
return 0;
}

G. The Witchwood

//By cls1277
#include<iostream>
#include<cstdio>
#include<queue>
#include<cstring>
#include<string>
#include<algorithm>
#include<cmath>
#include<vector>
#include<map>
#include<stack>
#include<sstream>
#include<set>
#include<cassert>
#include<bitset>
using namespace std;
typedef long long LL;
#define PI acos(-1)
#define INF 2147483647
#define eps 1e-7
#define Fo(i,a,b) for(LL i=(a); i<=(b); i++)
#define Ro(i,b,a) for(LL i=(b); i>=(a); i--)
#define Eo(i,x,_) for(LL i=head[x]; i; i=_[i].next)
#define Ms(a,b) memset((a),(b),sizeof(a))
#define lowbit(_) _&(-_)
#define ls x<<1
#define rs x<<1|1
#define endl 'n'
inline LL read() {
LL x = 0, f = 1;char c = getchar();
while (!isdigit(c)) { if (c == '-')f = -f;c = getchar(); }
while (isdigit(c)) x = (x << 1) + (x << 3) + (c ^ 48ll), c = getchar();
return x * f;
}
const LL maxn = 1005;
LL n , k , ans , a[maxn];
int main() {
ios::sync_with_stdio(false);
#ifdef DEBUG
freopen("data.txt","r",stdin);
#endif
cin>>n>>k;
Fo(i,1,n) cin>>a[i];
sort(a+1,a+n+1);
Ro(i,n,n-k+1) ans+=a[i];
cout<<ans;
return 0;
}

K. Scholomance Academy

//By cls1277
#include<iostream>
#include<cstdio>
#include<queue>
#include<cstring>
#include<string>
#include<algorithm>
#include<cmath>
#include<vector>
#include<map>
#include<stack>
#include<sstream>
#include<set>
#include<cassert>
#include<bitset>
using namespace std;
typedef long long LL;
#define PI acos(-1)
#define INF 2147483647
#define eps 1e-7
#define Fo(i,a,b) for(LL i=(a); i<=(b); i++)
#define Ro(i,b,a) for(LL i=(b); i>=(a); i--)
#define Eo(i,x,_) for(LL i=head[x]; i; i=_[i].next)
#define Ms(a,b) memset((a),(b),sizeof(a))
#define lowbit(_) _&(-_)
#define mk(_,__) make_pair(_,__)
#define pii pair<int,int>
#define ls x<<1
#define rs x<<1|1
#define endl 'n'
inline LL read() {
LL x = 0, f = 1;char c = getchar();
while (!isdigit(c)) { if (c == '-')f = -f;c = getchar(); }
while (isdigit(c)) x = (x << 1) + (x << 3) + (c ^ 48ll), c = getchar();
return x * f;
}
//const LL maxn = ;
int n,tp,fn,fp,tn;
double pre , ans;
struct Node {
char c;
int s;
Node(){};
Node(char cc , int ss) {
c=cc , s=ss;
}
bool operator < (const Node &a) {
if(s==a.s) return c>a.c;
return s>a.s;
}
};
vector<Node>a;
double tpr() {
return tp*1.0/(tp+fn);
}
double fpr() {
return fp*1.0/(tn+fp);
}
int main() {
//ios::sync_with_stdio(false);
#ifdef DEBUG
freopen("data.txt","r",stdin);
#endif
scanf("%dn",&n);
Fo(i,1,n) {
char ch; int sc;
scanf("%c%dn",&ch,&sc);
a.push_back(Node(ch,sc));
if(ch=='+') fn++;
else tn++;
}
sort(a.begin(),a.end());
for(int i=0; i<a.size(); i++) {
if(a[i].c=='+') fn--,tp++;
else tn--,fp++;
ans+=tpr()*(fpr()-pre);
pre=fpr();
}
printf("%.10lf",ans);
return 0;
}

最后

以上就是成就白昼为你收集整理的【补题日记】CF#744 Div.3 & 2020 ICPC沈阳站的全部内容，希望文章能够帮你解决【补题日记】CF#744 Div.3 & 2020 ICPC沈阳站所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。