AtCoder Regular Contest 091

最近这个三月在忙毕业的事情,答辩、各种表格、医院、签证等等。在结束这一切之后,这一期的AtCoder终于补完了。艰难脸^ - ^

C、D不用说什么的话,那一共才两道题。。。

Update: [2018-06-17]就这么一直拖到了现在。。。

题目链接

C - Flip,Flip, and Flip……

题意是给出了$n*m$个格子,然后每个格子都要进行翻转,连带着周围八个格子也都要翻转。问最终有多少格子是反面。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
ll n, m;
void solve()
{
cin >> n >> m;
ll ans = n*m;
int f = 0;
if (m >= 2)
{
f++;
ans -= 2 * n;
}
if (n >= 2)
{
f++;
ans -= 2 * m;
}
if(f==2)ans += 4;
cout << ans << endl;
}

D Remainder Reminder

找出不超过$n$中,有多少对$(a,b)$,使得$a\%b >= k$

枚举$b$。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
ll n, k;
void solve()
{
slla(n), slla(k);
ll ans = 0;
repp(x, k + 1, n)
{
ll f = n / x;
ll num = x - k;
ans += num*f;
ll sur = n%x + 1;
ans += max(sur - k, 0LL);
}
if (!k)ans = n*n;
cout << ans << endl;
}

E LISDL

给出$n,a,b$。构建一个长度为$n$的序列,元素是$1$到$n$。使得最长递增子序列长度为a,最长递减子序列长度为$b$。

这个题比较有趣了。。。可以先满足最长递增子序列为$a$,然后成段去构造最长递减子序列,这时也就可以发现满足条件是什么了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
ll n,a,b;
void solve()
{
slla(n),slla(a),slla(b);
if(a+b-1>n || a*b<n)
{
cout<<-1<<endl;
return;
}
while(n>0)
{
int x = min(a,n-b+1);
for(int i = n-x+1;i<=n;i++)
{
cout<<i<<" ";
}
n-=x;
b--;
}
}

F - Strange Nim

有$n$堆石子,每堆石子的数量为$A_i$,每堆石子都有一个参数$k_i$。现有a和b,分别进行如下操作:

选择一堆石子,如果当前该堆有$x$个石子,那么移除$[1, floor(x/k)]$。

不能进行操作的人判输。双方都是最优选择,问输赢情况。

sg找规律。。。

如果$n$整除$k$,那么sg(n,k)=n/k

发现g(1,k), g(2,k), g(3,k)…. g(n,k)中移除g(k,k) g(2*k,k), g(3*k,k)…数列没有变化。

如果$n$不整除$k$,那么假设n=k*x+b,有sg(x*k+b,k) = sg((x-1)*k+(b-1),k).

可以发现原来是x*k+b,现在要变成x*k+b-(x+1)。这里需要进行优化,计算有多少个x是不变的。一共要减ceil(b/(x+1))次,所以也就是(b+x)/(x+1)。

1
2
3
4
5
6
7
int SG(int a,int k)
{
int x=a/k,b=a%k;
if(!b) return x;
int t=(b+x)/(x+1);
return SG(a-t*(x+1),k);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
int n;
int cal(int x,int y)
{
if(x%y==0)
{
return x/y;
} else{
return cal(x - max(x%y/(x/y+1),1)*(x/y+1),y);
}
}
void solve()
{
sa(n);
int ans = 0;
repp(i,1,n)
{
int x,y;
sa(x),sa(y);
ans ^= cal(x,y);
}
if(ans)
{
puts("Takahashi");
}
else
{
puts("Aoki");
}
}