![Codeforces Round #760 (Div. 3),第1张 Codeforces Round #760 (Div. 3),第1张](/aiimages/Codeforces+Round+%23760+%28Div.+3%29.png)
Codeforces Round #760 (Div. 3)
E. Singers’ Tour
F. Reverse
G. Trader Problem
推推式子就行了。
int a[N];
int main()
{
int t;
scanf("%d", &t);
while(t --)
{
int n;
LL sum = 0;
scanf("%d", &n);
for(int i = 1;i <= n;i ++) scanf("%d", a+i), sum += a[i];
a[0] = a[n];
if(sum%(n*(n+1)/2))
{
puts("NO");
continue;
}
sum /= n*(n+1)/2;
for(int i = n;i >=1;i --)
{
if((sum-a[i]+a[i-1])%n || sum-a[i]+a[i-1]<=0)
{
puts("NO");a[1] = 0;break;
}
a[i] = (sum-a[i]+a[i-1])/n;
}
if(a[1])
{
puts("YES");
for(int i = 1;i <= n;i ++)cout<
爆搜, 写的很烦。
LL x, y;
string a, b;
mapma;
bool flag = 0;
string fan(string c) // 取反
{
string a = c;
while(a.back() == '0') a.pop_back();
reverse(a.begin(), a.end());
return a;
}
void inverse(LL x, string &a) // 转换成二进制字符串
{
while(x)a += (char)('0'+(x&1)), x>>=1;
reverse(a.begin(), a.end());
return ;
}
void dfs(string a)
{
if((a.size() > b.size() && a.back() == '1') || ma[a]) return ;
if(a.size() == b.size()) flag |= a == b|fan(a) == b;
ma[a] = 1;
if(a.back() == '0')
dfs(fan(a+'1')), dfs(fan(a));
else
{
ma[fan(a)] = 1;
dfs('1'+a); dfs(a+'1');
}
return ;
}
int main()
{
scanf("%lld%lld", &x, &y);
inverse(x, a); inverse(y, b);
dfs(a);
puts(flag ? "YES" : "NO");
return 0;
}
首先肯定要离线,然后还得把n+m个数排个序,那么就可以看作是一系列的连通块,连通块可以合并的条件是左边的最大值+k >= 右边的最小值,那么这就说明假设两个连通块内原本有a个数是n个数中的(a < n), 那么就可以从这两个连通块的范围内取最大的a个数。
写起来也有点绕,原本想直接set,但是太难写了,然后就改成了优先队列,但发现优先队列不能删除,如果要标记的话就要每个连通块的范围,但这样又想到了可以直接模拟,就直接模拟了,代码有注释
#include
#include
#include
#include
#include
#include
评论列表(0条)