Pro
Codeforces Round #744 (Div. 3)
The 2020 ICPC Asia Shenyang Regional Programming Contest
补题，不会写所有题目题解，请看清problem name
Sol
C. Ticks
比赛的时候忘记看这个题了 枚举题，枚举每一个
?
*
?，去看这个
?
*
?是否能组成“边长”大于等于k的两条边。
如果可以就给路过的所有
?
*
?打上标记，最后是否所有的
?
*
?均有标记就可以判断是否可以了。
D. Productive Meeting
开始的时候想到了第一大和第二大在一起贪心最好，但是仅仅比较了初始的最大和次大。
即，本题正确的贪心策略为：每次都是最大和次大交谈最好。贪心策略没想完整。
E2. Array Optimization by Deque
本题比E1仅仅多了求逆序对，这里我写的树状数组求逆序对。
所以每次直接往树状数组中值的位置加1就可以，然后判断应该放到前面还是后面。
如果放到前面，对应的是求
1
～
a
[
i
]
?
1
1\sim a[i]-1
1～a[i]?1的和；
如果放到后面，对应的是求
1
～
m
1\sim m
1～m（m为输入数据最大值）的和与
1
～
a
[
i
]
1\sim a[i]
1～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
a_i
ai?表示长度为
i
i
i时，r的个数，则区间(i,j)内r的个数为
a
j
?
a
i
?
1
a_j-a_{i-1}
aj??ai?1?
所以，当
a
j
a_j
aj?与
a
i
?
1
a_{i-1}
ai?1?的奇偶性不同时，r的个数为奇数。
注意，这里的
a
0
a_0
a0?可以取到，因为如果不取那么第一个位置就算不进去了。
这里
a
0
a_0
a0?的意义是前缀为空，r的个数为0。
容易想到，当全部为r时产生的结果一定最大，所以考虑全部为r时的答案。
此时一共有n+1种取法（因为有
a
0
a_0
a0?），所以根据
a
+
b
=
=
m
,
a
×
b
≤
?
m
2
?
?
m
2
?
a+b==m,a\times b\le \lfloor \frac{m}{2}\rfloor \lceil \frac{m}{2} \rceil
a+b==m,a×b≤?2m???2m??，因此第一问答案为：
?
n
+
1
2
?
?
n
+
1
2
?
\lfloor \frac{n+1}{2}\rfloor \lceil \frac{n+1}{2} \rceil
?2n+1???2n+1??
注意要开long long！！！
第二问，因为只要输出100个，所以搜索的复杂度可以接受。
这里我没用异或，因为我感觉直接判断会更加直观。
后面待更先上传/cy
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("%d\n",&n);
Fo(i,1,n) {
char ch; int sc;
scanf("%c%d\n",&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;
}
|