2019-2020 ICPC Southwestern European Regional Programming Contest (SWERC 2019-20)

猛男队友带飞,今日贡献only罚时
A、(zyj 1:41 +0)
给一张图,点和点之间的距离为欧几里得距离,要从起点到终点,有多种交通工具,每种的单位距离花费不同,求路长在B之内的最小花费。
建边求到每个位置时路径长为j的最小花费,用dij进行转移。

B、(zyj 0:04 +0)
给定n个字符串,求是否有哪个字符串出现次数严格超过一半
map即可

C、(wrf 0:13 +1)
求给定所有数中没出现过的最小的自然数
记录一下所有大小小于等于1e6的数,然后查找即可

D、(wrf 4:30 +5)
大模拟

E、

F、(wrf 0:47 +4)[……]

继续阅读

餐巾计划问题

题目链接
将每个点拆成白天和晚上,白天只收干净的餐巾,晚上只收脏餐巾,从源点往每天晚上连容量为x,费用为0的边,表示每天晚上会收到x条脏餐巾。
从每天早上往汇点连容量为x,费用为0的边,流满表示餐巾够用。
从每天晚上往下一天晚上连容量inf,费用0的边,表示留到下一天。
从每天晚上往快洗结束的那天早上连容量inf,费用快洗的边,表示快洗。
从每天晚上往慢洗结束的那天早上连容量inf,费用慢洗的边,表示慢洗。
从源点往每天早上连容量inf,费用买新餐巾的边,表示买餐巾
求最小费用最大流即可。

#include <bits/stdc++.h>
typedef long[......]

继续阅读

方格取数问题

题目链接
给n*m的方格图,然后取数,要求取出来的数的位置不相邻,问最大值。
因为每个点只对他四周的点有影响,那么将点进行奇偶分隔,然后源点向奇点连边,偶点往汇点连边,然后奇点往周围的偶点连边,跑出最大流即最小割,即要扣去的代价,用总和减去即可。


#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define inf 0x3f3f3f3f
const ll MAXN = 20000;
const ll maxm = 300000;
struct Edge{
	ll from[......]

继续阅读

试题库问题

题目链接
咕咕咕咕咕咕二个半月。。。。
给k个题目类型和n个题目,然后要求组成一套有\(a_i\)个i类试题的试卷,每个题目可以对应p类题目,但是只能作为一类使用,求组出的题目。
源点往题目连边1,题目往类型连边1,类型往汇点连需要个数,最大流。


#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define inf 0x3f3f3f3f
const ll MAXN = 6000;
const ll maxm = 300000;
struct Edge{
	ll from[......]

继续阅读

Educational Codeforces Round 86 (Rated for Div. 2)

AB不写了
C.Yet Another Counting Problem
给定a,b,给q个询问,要求在\([l,r]\)范围内求出\((i\ mod\ a)\ mod\ b!=(i\ mod\ b)\ mod\ a\)的数量。
打一下表可以发现,周期为lcm(a,b),里面符合的数为max(a,b)及以后的数。

还有一个方法,把a*b的前缀和表预处理出来,然后算一下有几组多几个然后就好了

D.Multiple Testcases
要求把n个问题分组,然后给定\(c_i\)从1-k表示大于等于i的问题数量不能超过\(c_i\)
问最少要分几组。
记录一下答案[……]

继续阅读

Codeforces Round #634 (Div. 3)

A、B、C、D队内基本都过了 就不写了
E.Three Blocks Palindrome
给n个数,让你找一个子序列,要求由x个a,y个b,x个a构成,x,y大于等于0,a,b可以相等,求最长的子序列的长度
n=2000的就没啥好讲的了 ,暴力基本都能过。
n=2e5 使用前缀和去优化,先将前缀和处理出来,然后开200个vector去把值为i的所有位置存起来,然后去枚举a从1到vector的长度/2,然后选择最优的b,如何选呢,枚举a的时候,贪心的选择最左和最右,那么就可以得到y个b所在的区间 ,用前缀和求区间的最大值即可。需要注意的是,这个方法在所有数都只出现1次的情况下,会输出0[……]

继续阅读

Educational Codeforces Round 85 (Rated for Div. 2)

A.Level Statistics
给n个时间递增的值,分别为游戏数和获胜数,判断是否正确。
首先游戏数和获胜数都是递增的,且获胜数不能超过游戏数,同时2个时间的增长的量也不能超过

#include <bits/stdc++.h>
using namespace std;
#define fr first
#define sc second
typedef long long ll;
const int N=1e5+5;
const int p=1e9+7;
ll qpow(ll a,ll n){ll res=1;while(n){if(n&1)res[......]

继续阅读

Codeforces Round #632 (Div. 2)

A.Little Artem
构建一个n*m的矩阵,填充上B和W,使得四周存在W的B的数量=四周存在B的W的数量+1。
解 如果n*m为奇数,那么BW交换填充即可,否则把第一个W改成B即可。

#include <bits/stdc++.h>
using namespace std;
#define fr first
#define sc second
typedef long long ll;
const int MAXN=1e5+5;
const int p=1e9+7;
ll qpow(ll a,ll n){ll res=1;while(n){if(n&am[......]

继续阅读

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[......]

继续阅读