Educational Codeforces Round 117 (Rated for Div. 2)

89 阅读 0 评论 59 点赞

我是靠谱客的博主健忘云朵，最近开发中收集的这篇文章主要介绍Educational Codeforces Round 117 (Rated for Div. 2)，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

a
稍微进行分类讨论

#include <iostream>
using namespace std;
#define eps 1e-8
const int maxn = 1e6;
void solve(){
int a, b, x, y; // c(x, y);
// A(0,0) B(x,y)
scanf("%d %d", &a, &b);
int dis_ac = x + y;
// 2x + 2y = a + b;
---- (1)
// 2abs(a-x) + 2abs(b-y) = a + b; 
//
a + b = 2a - 2x + 2b - 2y;
-->
2x + 2y = a + b; --- (2)
//
= 2a - 2x + 2y - 2b;
-->
2x - 2y = a - 3b; --- y = b, 2x = a - b
//
= 2x - 2a + 2b - 2y;
-->
2x - 2y = 3a - b;-- x = a, 2y = b - a 
//
= 2x - 2a + 2y - 2b;
-->
2x + 2y = 3a + 3b; 
//int dis_bc = abs(a-x) + abs(b-y);
if(b <= a and (a-b)%2==0) {
printf("%d %dn",(a-b)/2, b);
return ;
}
if(b >= a and (b-a)%2==0) {
printf("%d %dn",a, (b-a)/2);
return ;
}
int s1 = a + b;
for(int i = 0; i <= s1; i++) {
for(int j = 0; j <= s1; j++) {
if(2*i + 2*j == s1){
printf("%d %dn",i, j);
return ;
}
}
}
int s2 = 3*a + 3*b;
for(int i = 0; i <= s2; i++) {
for (int j = 0; j <= s2 ; j++) {
if(2*x + 2*y == s2) {
printf("ans = %d %dn", i, j);
return ;
}
}
}
printf("-1 -1n");
}
int main()
{
int t;
scanf("%d", &t);
while(t--)
solve();
return 0;
}

前半部分要求有个最小，那么除了那个之外，其他的从大到小放
要求后半部分有个最大，那么除了那个之外，其他的放剩下的
最后特判一下两个位置，如果不发生冲突输出

#include <iostream>
#include <algorithm>
using namespace std;
int neg[210], ans[210];
bool vis[210];
int main()
{
int t;
scanf("%d", &t);
while(t--)
{
int n, a, b;
scanf("%d %d %d",&n, &a, &b);
for(int i = 1; i <= n; i++) neg[i] = i,vis[i] = false;
ans[1] = a;
ans[n] = b;
vis[a] = true;
vis[b] = true;
int cnt1 = 1;
for(int i = n; i >= 1; i--) {
if(cnt1>=n) break;
if(!vis[i]) {
ans[++cnt1] = neg[i];
vis[i] = true;
}
}
cnt1 = n-1;
for(int i = 1; i <= n-1 ;i++){
if(cnt1 <= n) break;
if(!vis[i]) {
ans[cnt1--] = neg[i];
vis[i] = true;
}
}
bool flag = false;
if(n==2) flag = true;
else if(ans[n/2] > ans[1] and ans[n] > ans[n/2+1]) flag = true;
if(flag==true)
for(int i = 1; i <= n; i++) {
if(i < n) printf("%d ", ans[i]);
else printf("%dn",ans[i]);
}
else puts("-1");
}
return 0;
}

c
分类讨论：
（1）对于每个k，最多有 $k^2$ 个星星，如果 x 大于这个值，直接输出
（2）行数到达k的这些行，是一个公差为1的等差递增数列，对其前缀和做二分就行了
（3）行数大于k的这些行，是一个公差为1的等差递减数列，还是做二分，找对应的行。

#include <iostream>
#include <algorithm>
using namespace std;
#define LL long long
LL k, x;
void init()
// 通过打表发现对于一个k， 有 k*k 个
{
int cnt = 0;
int n; scanf("%d", &n);
int sum = 1;
for(int i = 1; i <= n; i++)
{
cnt += sum++;
}
sum--;
for(int i = 1; i <= n-1; i++) {
cnt += --sum;
}
cout << cnt << endl;
}
int main()
{
//init();
int t;
scanf("%d", &t);
while(t--)
{
scanf("%lld %lld",&k, &x);
if(x >= k*k) printf("%lldn",2*k-1);
else if(k*(1+k)/2 >= x){
LL l = 1LL, r = k;
while(l < r){
LL mid = (l + r) >> 1;
if(mid*(mid+1)/2 >= x) r = mid;
else l = mid + 1;
}
printf("%lldn",r);
}
else {
x -= k*(k+1)/2; // x = 14
// x = 4
// k = 4
LL l = 1LL, r = k-1; // l = 1, r = 2
while(l < r){
LL mid = (l + r) >> 1; // 1
// 
if((k-1+k-mid)*mid/2 >= x) r = mid;
else l = mid + 1;
}
printf("%lldn",r+k);
}
}
return 0;
}

保证a 大于 b
看了代码还是很好理解的

#include <iostream>
#include <algorithm>
#include <vector>
#include <queue> 
using namespace std;
typedef long long LL;
LL f(LL a, LL b, LL x)
{
if(b==0) return x == a;
if(x <= a and x % b == a % b) return 1;
return f(b, a%b, x);
}
int main()
{
int t;
scanf("%d",&t);
while(t--)
{
LL a, b, x;
scanf("%lld %lld %lld",&a, &b, &x);
bool flag = false;
if(a<b) swap(a, b);
if(f(a,b,x)) flag = true;
if(flag)puts("YES");
else puts("NO");
}
return 0;
}