时隔一个月重返coding……
期末复习了一个月也不亏 倒是都过了……
就是计组61有点亏 复变68也太低了 其他都还好……
假期做的第一场cf 三道题 还可以……
最后room第三 standing383简直人生巅峰……
看楼上楼下都是两道题的 如果A题不错那么多估计能进前300了吧……
这场倒是把之前两场的分加回来了 开头不错 这个假期争取紫名~
A.Lesha and array splitting
把给定的数组分割成几个区间 要求各个区间和不能为0
一开始没注意到分割之后的区间重新合成之后还是这个区间错了好几发……
具体思路见注释
#include <bits/stdc++.h>
using namespace std; int a[]; int main()
{
int n;
int p = -, sum = ;
scanf("%d",&n);
for (int i = ; i <= n; i ++)
{
scanf("%d",&a[i]);
sum += a[i];
if (a[i] != && p == -)
{
p = i;
}
}
if (p == -)
{//都是零的话肯定不行
puts("NO");
}
else
{
puts("YES");
if (sum != )
{//数列和不为零 那么一个区间就够了
printf("1\n1 %d\n",n);
}
else
{//数列和为零的话 取最前面的分割点就好了
printf("2\n1 %d\n%d %d\n", p, p+, n);
}
}
return ;
}
B.Ilya and tic-tac-toe game
题意就是问该下的人再下一步能不能赢
4x4的格子强行暴力
#include <bits/stdc++.h>
using namespace std; char mp[][],one; int main()
{
int nx=,no=;
for(int i=; i<; i++)
{
gets(mp[i]);
for(int j=; j<; j++)
{
if(mp[i][j]=='x') nx++;
if(mp[i][j]=='o') no++;
}
}
if(no==nx) one='x';
else one='o';
bool ok=false;
for(int i=; i<; i++)
{
for(int j=; j<; j++)
{
if(mp[i][j]=='.') //这个地方是空的 假如把棋子下在这
{
mp[i][j]=one;
for(int k=; k<; k++)
{
for(int l=; l<; l++)
{
if(k < && mp[k][l] == one && mp[k+][l] == one && mp[k+][l] == one) ok=true;
if(l < && mp[k][l] == one && mp[k][l+] == one && mp[k][l+] == one) ok=true;
}
}
if(mp[][] == one && mp[][] == one && mp[][] == one) ok = true;
if(mp[][] == one && mp[][] == one && mp[][] == one) ok = true;
if(mp[][] == one && mp[][] == one && mp[][] == one) ok = true;
if(mp[][] == one && mp[][] == one && mp[][] == one) ok = true;
if(mp[][] == one && mp[][] == one && mp[][] == one) ok = true;
if(mp[][] == one && mp[][] == one && mp[][] == one) ok = true;
if(mp[][] == one && mp[][] == one && mp[][] == one) ok = true;
if(mp[][] == one && mp[][] == one && mp[][] == one) ok = true;
if(ok)
{
printf("YES");
return ;
}
else mp[i][j]='.'; //没赢 换个地方下
}
}
}
printf("NO\n");
return ;
}
C.Vladik and chat
是个大模拟 还没弄明白……
D.Fedor and coupons
数据结构题
给你n个区间 选择k个求最长交集
自己做没做出来 和别人交流了一下才知道是个堆 现学现卖了一发
写了一个堆 维护前k大值 假设区间i作为最后一个区间必选
ans=max(前i-1个区间右端点的k-1大值，第i区间右端点的最小值) - 第i个区间左端点
#include<bits/stdc++.h>
using namespace std; const int maxn=3e5+; struct A
{
int x, y, id;
} a[maxn]; bool cmp(A x,A y)
{
return x.y == y.y ? x.x < y.x : x.y > y.y;
} priority_queue<int> q;
int ans = , r = -,n, k; void solve() //优先队列维护k大值
{
q.push(-2e9);
for (int i = ; i < n; i ++)
{
if (q.size() == k)
{
int l = max(q.top(), a[i].x);
if (a[i].y - l + >= ans)
{
ans = a[i].y - l + ;
r = a[i].y;
}
}
q.push(a[i].x);
if (q.size() > k)
{
q.pop();
}
}
} void print()
{
if(ans)
{
int l = r - ans + ;
for (int i = ; k > ; i ++)
{
if (a[i].x <= l && a[i].y >= r)
{
k --;
printf("%d ",a[i].id);
}
}
}
else
{
for (int i = ; i < k; i ++)
{
printf("%d ",a[i].id);
}
}
} int main()
{
scanf("%d%d",&n,&k);
for (int i = ; i < n; i ++)
{
scanf("%d%d",&a[i].x,&a[i].y);
a[i].id = i + ;
}
sort(a, a + n, cmp); //按区间边界排序
solve();
printf("%d\n",ans);
print();
return ;
}
/* */
E.Dasha and cyclic table
没看懂……
巨巨们讨论的热火朝天 我却啥都听不懂……
等能听懂他们说啥应该就有很大进步了吧……