Preface
和昨天刚好相反，前期极度崩盘2h2题而且一堆银铜牌题不会
但好在后面稳扎稳打慢慢追回来了一点，最后超高罚时8题收场
这场一边打一边看ECF的实况，最后看到同校的Wifi暴打全场，实在是ORZ
A. Access Denied
签到，首先暴力问出长度然后从前往后一位一位确定即可
注意实现的时候不需要特意去算返回的秒数的含义，只要找一个和其它返回结果不同的即可
#include<cstdio>
#include<iostream>
#include<string>
#include<cstdlib>
#define RI register int
#define CI const int&
using namespace std;
inline int ask(string s)
{
cout<<s<<endl;
string t; getline(cin,t);
if (t[7]=='G') exit(0);
int ret=0; for (RI i=15;;++i)
if (t[i]>='0'&&t[i]<='9') ret=ret*10+t[i]-'0'; else break;
return ret;
}
int main()
{
for (;;)
{
RI i,j,k; int res[100],len;
for (i=1;i<=20;++i)
{
string s(i,'a'); res[i]=ask(s);
}
for (i=1;i<=20;++i)
{
bool flag=1; for (j=1;j<=20;++j)
if (i!=j&&res[i]==res[j]) { flag=0; break; }
if (flag) { len=i; break; }
}
string ans="";
for (i=1;i<=len;++i)
{
for (j=1;j<=62;++j)
{
string s=ans;
if (j>=1&&j<=26) s+='a'+j-1;
if (j>=27&&j<=52) s+='A'+j-27;
if (j>=53&&j<=62) s+='0'+j-53;
for (k=1;k<=len-i;++k) s+='a';
res[j]=ask(s);
}
for (j=1;j<=62;++j)
{
bool flag=1; for (k=1;k<=62;++k)
if (j!=k&&res[j]==res[k]) { flag=0; break; }
if (flag)
{
if (j>=1&&j<=26) ans+='a'+j-1;
if (j>=27&&j<=52) ans+='A'+j-27;
if (j>=53&&j<=62) ans+='0'+j-53;
break;
}
}
}
ask(ans);
}
return 0;
}
B. Boredom Buster
另一个好难的交互，题都没看
C. Cutting Edge
最近每次我正序开题都能开到防AK题，继承徐神特性了属于是
D. Dyson Circle
徐神比赛时提出的做法思路比较自然，把一个关键格子的四个角的坐标都标出来，然后对所有标出来的点跑一个凸包
最后将凸包上的相邻点连接起来几个，贡献就是两点间横纵坐标之差取\(\max\)
但写完遇到第三个样例发现需要修正，当所有点在同一条对角线上时答案需要加\(1\)，这个手玩下第三个样例很好理解
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N = 2e5+5;
int n;
int stk[N*4], top=-1;
struct Pt{
int x, y;
int crs(Pt b){return x*b.y-y*b.x;}
Pt operator-(Pt b)const{return Pt{x-b.x, y-b.y};}
bool operator<(Pt b)const{return x!=b.x ? x<b.x : y<b.y;}
}pt[N*4];
int makeCH(){
int sz = n*4;
sort(pt, pt+sz);
stk[++top] = 0;
for (int i=1; i<sz; ++i){
while (top>0 && (pt[stk[top]]-pt[stk[top-1]]).crs(pt[i]-pt[stk[top-1]])<=0) --top;
stk[++top] = i;
}
int mx = top;
for (int i=sz-2; i>=0; --i){
while (top>mx && (pt[stk[top]]-pt[stk[top-1]]).crs(pt[i]-pt[stk[top-1]])<=0) --top;
stk[++top] = i;
}
return top;
}
signed main(){
ios::sync_with_stdio(0); cin.tie(0);
cin >> n;
if (n==1){
cout << 4 << '\n';
return 0;
}
int t1=0, t2=0;
bool ok1=true, ok2=true;;
for (int i=0; i<n; ++i){
int x, y; cin >> x >> y;
if (0==i) t1=x+y, t2=x-y;
else{
if (t1!=x+y) ok1=false;
if (t2!=x-y) ok2=false;
}
pt[i*4+0].x = x, pt[i*4+0].y = y;
pt[i*4+1].x = x+1, pt[i*4+1].y = y;
pt[i*4+2].x = x, pt[i*4+2].y = y+1;
pt[i*4+3].x = x+1, pt[i*4+3].y = y+1;
}
int sz = makeCH();
// for (int i=0; i<sz; ++i){
// printf("(%d %d)\n", pt[stk[i]].x, pt[stk[i]].y);
// }
int ans=0;
for (int i=0; i<sz; ++i){
ans += max(abs(pt[stk[i]].x-pt[stk[(i+1)%sz]].x), abs(pt[stk[i]].y-pt[stk[(i+1)%sz]].y));
}
if (ok1 || ok2){
cout << ans + 1 << '\n';
}else cout << ans << '\n';
return 0;
}
PS：赛后看了题解做法发现原来很trivial，最后的答案一定是个大的斜矩形，不过特判还是避免不了的
E. Exchange Students
挺有意思的一个题，最后20min才有时间看，之后有时间仔细想想
F. Flatland Olympics
徐神秒出思路最后祁神顶住压力上去快速过了这个题，那我在干嘛（原来是在边上打雀魂）
首先特判掉点在跑道延长线上的情况，以及另外一些奇奇怪怪的边界问题
然后可以沿着线段所在的直线把平面分成两块，显然每一块的求解是独立的
对于每一块，不妨从跑道的某个端点为起点对所有点做一个极角排序，然后把这个排名记为这个点的第一位特征
以此类推对于跑道的另一个端点也搞出一个排名，然后画画图会发现题目要求的等价于一个二维偏序问题
直接排序后用树状数组维护下即可，总复杂度\(O(n\log n)\)
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N = 2e5+5;
int n;
struct Pt{
int x, y;
int crs(Pt b){return x*b.y-y*b.x;}
int dot(Pt b){return x*b.x+y*b.y;}
Pt operator-(Pt b)const{return Pt{x-b.x, y-b.y};}
}pt[N];
int cross(Pt p, Pt a, Pt b){return (a-p).crs(b-p);}
struct Fenwick{
int cnt[N];
int lb(int x){return x&(-x);}
void upd(int pos, int val){for (int i=pos; i<=n; i+=lb(i)) cnt[i]+=val;}
int qry(int pos){int res=0; for (int i=pos; i>0; i-=lb(i)) res+=cnt[i]; return res;}
void init(){for (int i=1; i<=n; ++i) cnt[i]=0;}
}fen;
vector<int> up, dn, line1, line2;
int px[N], py[N], idx=0, idy=0;
int solve1(Pt s0, Pt e0, vector<int> &vec){
if (vec.empty()) return 0;
memset(px, 0, (n+1)*sizeof(int));
memset(py, 0, (n+1)*sizeof(int));
sort(vec.begin(), vec.end(), [&](int a, int b){
return cross(s0, pt[a], pt[b])>=0;
});
idx=idy=0;
px[vec[0]]=++idx;
for (int i=1; i<(int)vec.size(); ++i){
if (cross(s0, pt[vec[i]], pt[vec[i-1]])!=0) ++idx;
px[vec[i]] = idx;
}
sort(vec.begin(), vec.end(), [&](int a, int b){
return cross(e0, pt[a], pt[b])<=0;
});
py[vec[0]]=++idy;
// printf("i=%d (%lld %lld)\n", 0, pt[vec[0]].x, pt[vec[0]].y);
for (int i=1; i<(int)vec.size(); ++i){
// printf("i=%d (%lld %lld)\n", i, pt[vec[i]].x, pt[vec[i]].y);
if (cross(e0, pt[vec[i]], pt[vec[i-1]])!=0) ++idy;
py[vec[i]] = idy;
}
sort(vec.begin(), vec.end(), [&](int a, int b){
return px[a]!=px[b] ? px[a]<px[b] : py[a]<py[b];
});
// printf("vec:"); for (int x : vec) printf("%lld ", x); puts("");
// printf("px:"); for (int i=1; i<=n; ++i) printf("%lld ", px[i]); puts("");
// printf("py:"); for (int i=1; i<=n; ++i) printf("%lld ", py[i]); puts("");
fen.init();
int res=0;
for (int a : vec){
// printf("a=%d px=%d py=%d\n", a, px[a], py[a]);
res += fen.qry(py[a]);
fen.upd(py[a], 1);
}
return res;
}
signed main(){
ios::sync_with_stdio(0); cin.tie(0);
Pt s, e;
cin >> s.x >> s.y >> e.x >> e.y;
cin >> n;
for (int i=1; i<=n; ++i){
cin >> pt[i].x >> pt[i].y;
int crs = cross(s, e, pt[i]);
if (crs>0) up.push_back(i);
else if (crs<0) dn.push_back(i);
else{
if ((e-s).dot(pt[i]-s)>0) line1.push_back(i);
else line2.push_back(i);
}
}
int ans=0;
ans += solve1(s, e, up);
ans += solve1(e, s, dn);
// printf("ans=%lld\n", ans);
// printf("l1=%lld l2.size=%lld\n", line1.size(), line2.size());
ans += (int)(line1.size()-1)*line1.size()/2;
ans += (int)(line2.size()-1)*line2.size()/2;
cout << ans << '\n';
return 0;
}
G. Glossary Arrangement
祁神和徐神写的，我题目都没看，好像是二分行数后套个DP检验一下
#include<bits/stdc++.h>
using namespace std;
const int N = 5e3+5;
int n, w;
string str[N];
int f[N], g[N], path[N], width[N], wd[N];
int mp[N][N];
int check(int x){
memset(f, 0, sizeof(n+1));
f[0]=-1, g[0]=0, path[0]=0;
for (int i=1; i<=n; ++i){
int len=str[i].length();
f[i] = 1e9, g[i]=i;
for (int j=i-1; j>=0 && i-j<=x; --j){
// printf("i=%d j=%d len=%d\n", i, j, len);
if (f[j]+len+1 < f[i]){
f[i] = min(f[i], f[j]+len+1);
g[i] = g[j]+1;
path[i] = j;
wd[i] = len;
}
len = max(len, (int)str[j].length());
// if (str[j].length() > str[i].length()) break;
}
}
if (f[n]>w) return false;
else return true;
}
void print(int r, int c){
if (mp[r][c]==0) for (int i=0; i<=width[c]; ++i) cout << ' ';
else{
cout << str[mp[r][c]];
for (int i=str[mp[r][c]].length(); i<=width[c]; ++i) cout << ' ';
}
}
signed main(){
ios::sync_with_stdio(0); cin.tie(0);
cin >> n >> w;
for (int i=1; i<=n; ++i) cin >> str[i];
int L=1, R=n;
while (L<R){
int M = L+(R-L)/2;
// printf("L=%d R=%d M=%d\n", L, R, M);
int mx=-1;
if (check(M)) R=M;
else L=M+1;
// printf("L=%d R=%d mx=%d\n", L, R, mx);
// printf("f:"); for (int i=1; i<=n; ++i) printf("%d ", f[i]); puts("");
// printf("g:"); for (int i=1; i<=n; ++i) printf("%d ", g[i]); puts("");
// printf("path:"); for (int i=1; i<=n; ++i) printf("%d ", path[i]); puts("");
}
check(L);
// printf("R=%d, C=%d\n", L, g[n]);
int cur=n, lst=path[n], r=cur-lst, c=g[n];
// printf("r=%d, c=%d cur=%d\n", r, c, cur);
width[c] = wd[n];
while (cur>0){
if (cur == lst){
// printf("cur=%d lst=%d\n", cur, lst);
lst = path[cur];
--c;
r=cur-lst;
width[c] = wd[cur];
}
mp[r][c] = cur;
--r;
--cur;
}
// for (int i=0; i<=L; ++i){
// for (int j=0; j<=g[n]; ++j){
// printf("%d ", mp[i][j]);
// }puts("");
// }
cout << L << ' ' << g[n] << '\n';
for (int i=1; i<=g[n]; ++i) cout<< width[i] << (i==g[n] ? '\n' : ' ');
for (int i=1; i<=L; ++i){
for (int j=1; j<=g[n]; ++j){
print(i, j);
}cout << '\n';
}
return 0;
}
H. Heating Up
徐神前面提了个笛卡尔树的做法，后面我感觉如果真是这样的话过的人肯定没这么多，后面搞了个相对简单的做法直接艹了过去
首先答案具有二分性，考虑如何check，首先要注意到我们将原序列倍长后处理和在环上处理是等价的
然后考虑如果选择了某个起点，最后扩展出的区间是\([l,r]\)，那么显然以\([l,r]\)中的任何一个点作为起点扩展出的区间都是\([l,r]\)，就无需再考虑了
但如果直接上按顺序扫描一遍来做的话又会有一个问题就是向前扩展时带来的复杂度消耗很大
因此我们不妨搞个双向链表，然后扩展的时候把点合并一下就能保证复杂度了，具体实现可以看代码
#include<cstdio>
#include<iostream>
#define int long long
#define RI register int
#define CI const int&
using namespace std;
const int N=1e6+5;
int n,s[N],a[N],b[N],L[N],R[N];
inline bool check(CI st)
{
RI i; for (i=1;i<=n;++i) a[i]=a[i+n]=b[i]=b[i+n]=s[i];
for (i=1;i<=2*n;++i) L[i]=i-1,R[i]=i+1;
R[0]=1; L[2*n+1]=2*n; a[0]=a[2*n+1]=6e18;
for (i=1;i<=2*n;i=R[i])
{
if (a[i]>st) continue;
int tmp=st+b[i];
auto remove=[&](CI x)
{
int pre=L[x],nxt=R[x];
R[pre]=nxt; L[nxt]=pre;
};
for (;;)
{
if (a[L[i]]>tmp&&a[R[i]]>tmp) break;
if (a[L[i]]<=tmp)
{
a[i]=min(a[i],a[L[i]]);
b[i]+=b[L[i]]; tmp+=b[L[i]]; remove(L[i]);
}
if (a[R[i]]<=tmp)
{
a[i]=min(a[i],a[R[i]]);
b[i]+=b[R[i]]; tmp+=b[R[i]]; remove(R[i]);
}
}
}
return R[R[0]]==2*n+1;
}
signed main()
{
RI i; for (scanf("%lld",&n),i=1;i<=n;++i) scanf("%lld",&s[i]);
int l=0,r=1e13,mid,ret; while (l<=r)
if (check(mid=l+r>>1)) ret=mid,r=mid-1; else l=mid+1;
return printf("%lld",ret),0;
}
I. IXth Problem
题目都没看，弃疗
J. Jet Set
妈的因为没判经度相同的情况一直WA给我写红温了，过了这题后全队的节奏就对起来了
首先注意到纬度是没有用的，而每次相邻的两点大圆航线总是会走经度变化较少的一边
而如果出现两个点经度差恰好为\(180\degree\)，那么它们的大圆航线一定过极点
因此特判上面那种情况后拿个数组模拟一下即可，至于处理\(.5\)经度的话把所有点下标乘\(2\)最后再除即可
#include<cstdio>
#include<iostream>
#define RI register int
#define CI const int&
const int N=1005,S=360;
int n,phi,d[N],vis[N];
int main()
{
RI i,j; for (scanf("%d",&n),i=1;i<=n;++i) scanf("%d%d",&phi,&d[i]);
for (d[n+1]=d[1],j=1;j<=n;++j)
{
int s=d[j]*2,t=d[j+1]*2;
if (abs(s-t)==360) return puts("yes"),0;
if (s==t) { vis[s+S]=1; continue; }
if (t>s&&t-s<360)
{
for (i=s;i<=t;++i) vis[i+S]=1;
} else
if (t<s&&(360-s)+(t+360)<360)
{
for (i=s;i<360;++i) vis[i+S]=1;
for (i=-360;i<=t;++i) vis[i+S]=1;
} else
if (t<s&&s-t<360)
{
for (i=t;i<=s;++i) vis[i+S]=1;
} else
{
for (i=t;i<360;++i) vis[i+S]=1;
for (i=-360;i<=s;++i) vis[i+S]=1;
}
}
int pos=360; for (i=-360;i<360;++i) if (!vis[i+S]) pos=i;
if (pos==360) return puts("yes"),0;
int x=pos/2,y=pos%2?5:0;
if (pos==-1) puts("no -0.5"); else printf("no %d.%d",x,y);
return 0;
}
K. Knitpicking
签到，直接枚举最后配对的是那种袜子
对于其它的袜子，要么在左右脚中取较大的一个，要么取一个任意脚的
#include<bits/stdc++.h>
using namespace std;
int n;
struct Sock{
int a, l, r;
};
map<string, Sock> mp;
signed main(){
ios::sync_with_stdio(0); cin.tie(0);
cin >> n;
for (int i=1; i<=n; ++i){
string s1, s2;
int cnt;
cin >> s1 >> s2 >> cnt;
if (s2[0]=='a'){
mp[s1].a=cnt;
}else if (s2[0]=='l'){
mp[s1].l=cnt;
}else if (s2[0]=='r'){
mp[s1].r=cnt;
}
}
bool ok=false;
int ans=0;
// for (auto [a, l, r] : mp){
for (auto it = mp.begin(); it!=mp.end(); ++it){
auto [a, l, r] = it->second;
// a = it->a, l=it->l, r=it->r
if (a>=2 || (l>0&&r>0)) ok=true;
ans += max(max(l, r), (a>0 ? 1 : 0));
}
if (!ok) cout << "impossible\n";
else cout << ans+1 << '\n';
return 0;
}
L. Lucky Shirt
这题前面徐神提了一堆诸如模拟若干次的做法，但后面我灵光一闪发现一个关键点就迎刃而解了
首先这题最关键的就是要注意到这题的操作是“无前效性”的，比如我们找到最终操作的最大长度\(x\)，则所有操作的影响可以看作只进行了一次长度为\(x\)的打乱操作
因此这题的思路就很简单了，先考虑求\(f(x)\)表示进行的\(k\)次操作中最大的打乱长度为\(x\)的概率
这个可以用经典容斥，设\(g(x)\)表示进行的\(k\)次操作中最大的打乱长度为\(\ge x\)的概率，则\(g(x)=1-(\frac{x-1}{n})^k\)，同时\(f(x)=g(x)-g(x+1)\)
然后知道\(f(x)\)后我们简单讨论下即可：
- \(x<i\)，则这次操作不会对\(i\)位置产生影响，贡献为\(f(x)\times i\)
- \(x\ge i\)，则这次操作会把\(i\)等概率地打乱到\([1,x]\)中，贡献为\(f(x)\times \frac{1+x}{2}\)
#include <bits/stdc++.h>
using real = long double;
real ksm(real a, int b) {
real r = 1.0L;
while(b) {
if(b & 1) r = r * a;
a = a * a;
b >>= 1;
}
return r;
}
int n, i, k;
real g(int x) {
return 1 - ksm(real(x - 1) / n, k);
}
real f(int x) {
return g(x) - g(x + 1);
}
int main() {
std::cin >> n >> i >> k;
std::cout << std::fixed << std::setprecision(20);
real ans = 0;
for(int j = 1; j < i; ++j) ans += i * f(j);
for(int j = i; j <= n; ++j) ans += real(j + 1) * f(j) * 0.5L;
std::cout << ans << char(10);
return 0;
}
Postscript
明天找场简单点的提提信心，今天前面差点红温爆炸了说是
- 2021 Northwestern Programming European Regional2021 northwestern programming european 2019 northwestern programming european programming acm-icpc american regional programming shenyang regional contest programming hangzhou regional contest regional contest macau 2021 programming regional contest 2023 programming regional yinchuan contest programming stormwind shenyang regional intercollegiate programming regional contest