Codeforces Round #628 (Div. 2)

A.
写2个数,使得gcd(a,b)+lcm(a,b)=x;
解  1和x-1即可。

#include <bits/stdc++.h>
using namespace std;
#define fr first
#define sc second
typedef long long ll;
void work()
{
    int n;
    scanf("%d",&n);
    printf("%d %d\n",n-1,1);
}
int main()
{
    ios_base::sync_with_stdio(0); cin.t[......]

继续阅读

Codeforces Round #627 (Div. 3)

A.
给n个数,可以进行无限次操作,每次可以使某个数+2,或者使所有数-1,问能否使得最后都为0
解 因为只能单个+2和总体-1,那么奇偶性不变,判断全奇全偶即可

#include <bits/stdc++.h>
using namespace std;
#define fr first
#define sc second
typedef long long ll;
int b[2];
void work()
{
    b[0]=b[1]=0;
    int n;
    scanf("%d",&n);
    for(int i=1;i&l[......]

继续阅读

Educational Codeforces Round 83

赛后看来这场还是挺简单的,还是太菜了

A
给正n边形和正m边形,问是否m上的所有点都在n的点上。
解 判断m%n即可。

#include <bits/stdc++.h>
using namespace std;
#define fr first
#define sc second
typedef long long ll;
void work()
{
    int n,m;
    scanf("%d%d",&n,&m);
    if(n%m==0){
        printf("YES\n");
    }else pri[......]

继续阅读

Codeforces Round #626

div2A
给n个数,从中取出任意个数使得和为偶数,给出取出的数量和取出的数的位置。
解 2个奇数或者1个偶数即可。

#include <bits/stdc++.h>
using namespace std;
#define fr first
#define sc second
typedef long long ll;
int a[105];
void work()
{
	int n;
	scanf("%d",&n);
	for(int i=1;i<=n;i++){
		scanf("%d",&a[i]);
	}
	int c[......]

继续阅读

最长不下降子序列

给你n个数,第一问要求求出最长不下降子序列长度s,第二问在每个数字只使用一次的情况下,求出长度为s的不下降子序列有多少个,第三问\(a_1\)和\(a_n\)可以使用无限次的情况下长度为s的不下降子序列有多少个。
解 第一问用n^2的lis求解,并存dp[i]为从1到i的最长不下降子序列长度,然后因为每个点只能使用一次,所以使用拆点,对于dp[i]为1的地方,建源点往i.x边权为1,对于dp[i]为s的地方建i.y往汇点边权为1,然后对于每个i,建i.x往i.y边权为1(保证每个点只会使用一次),然后对于满足\(i>j\)并且\(a_i>=a_j\)并且\(dp[a_i]==dp[……]

继续阅读

圆桌问题

有m个单位,每个单位有\(r_i\)个人,要分配到n张桌子,每个桌子可以容纳\(c_i\)的人,要求相同单位的人不能同一张桌子上,问能否分配及分配方法。
解 很显然的一道网络流,源点往单位建单位人数的边,桌子往汇点建容纳人数的边,每个单位向每个桌子建流量为1的边,这样可以保证每个单位最多只有1个人在每张桌子上,跑最大流即可。


#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define inf 0x3f3f3f3f
const ll MAXN = 1000;
const ll[......]

继续阅读

魔术球问题

给n个柱子,要依次放入1,2,3,……的球,要求每根柱子相邻的球的和为完全平方数,问最多能放几个球。
可以理解为 你最多可以有多少个球把他们分成n组。同样使用最小边覆盖=点数-最大匹配
先拆成二分图,在和为平方数的点之间加边,源点往x连,汇点往y连。不断加入新点,跑新的最大流(新的是多出来的,所以要用sum加起来),然后判断总数-maxflow>n时跳出。


#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define inf 0x3f3f3f3f
const ll MAX[......]

继续阅读

最小路径覆盖问题

给一个有向无环图,要求你用最少的路径(所有路径不重复经过一个点)包含图中所有点,最少需要几条路径。
最小边覆盖=总数-最大匹配。先一开始当n条,然后考虑路径合并,每有两条路径合在一起,那么覆盖数就-1。所以,将点拆成x和y,源点向x连1,y向汇点连1,然后把给的边从x连到y,这样跑出的最大流即是路径合并的数量,减一下即可。


#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define inf 0x3f3f3f3f
const ll MAXN = 1000;
const ll m[......]

继续阅读

太空飞行计划

有n个实验,每个实验有一定的收益,同时每个实验需要一定的仪器,仪器需要一定的代价,问最多收益。
解 先假设所有实验收益都得到,然后就有2种损失,要么损失掉这个实验的收益(即不需要买仪器),或者损失掉仪器的价格(获得该实验的收益)。源点往实验连实验的收益,仪器往汇点连仪器的价格,实验往仪器连inf(防止被割掉),求最小割,减一下。


#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define inf 0x3f3f3f3f
const ll MAXN = 1000;
const l[......]

继续阅读