UPD：变色了！！！历史最高1618~
Educational Codeforces Round 81 (Rated for Div. 2)
The 2019 University of Jordan Collegiate Programming Contest
充实的一天，打两场可还行。补的一些题记录一下。
edu81
Educational Codeforces Round 81 (Rated for Div. 2)
还不知道上分还是掉分，还挺可惜的，被B卡了没做出来，C也调了一会儿答案的更新，反而是D做的很快，D直接秒了嘻嘻，大半夜的挺高兴。要是没出CD就血掉分勒。
赛后hack三个别人的B，才知道edu的hack不加分，为啥子勒？、
这题我自己光判断-1的条件就想错了，什么情况有无限的？只有当每个循环节的贡献产出为0（ 我们记循环节贡献产出为cir），并且一个循环节内有符合的答案，就是无限个。
这个不难理解，就是存在某个或者某些位置有答案，并且之后的每个循环节的这个位置都依然有答案。
那怎么保证别的情况的答案不是无限呢？这也可以理解(赛中的我没有意识到)，如果某个位置的答案符合，那么 cir 或正或负必然会将别的循环节的这个数给搞得不一样。
然后口胡证明完毕。经过这样的思考，我们就发现，一般的情况来说（cir不为0），每个位置最多只有一次答案。
只需观察是否有 k*cir+cur==x k>=0.
cur表示遍历到当前位置的值 cnt0-cnt1的值。k>=0也是必要的。
然后我这里也搞的很失败， 我一直用的 x%cir==cur？这样的 在x与cir正负不一致的情况，十分的混乱而难搞，无法保证正确性，而且无法保证k的非负性。
（个人理解，有兴趣也可以查阅下对负数取模的问题，我看了感觉稍微明白了一些，都是向0取整，正确性似乎可以，k的非负性的就无法保证了）
不过可以把这个式子稍微改写下，就是 ( (x-cur )%cir ==0 && (x-cur)/cir >= 0 ) 用这样一个式子 就非常的完美啦。 保证是倍数，保证有串长不会负(滑稽。
hack别人的时候很多人特判正负的情况，其实还蛮麻烦的我感觉。
然后老生常谈 puts 不要和关同步的cin cout混用，我补的时候puts("-1")那里出大问题。开同步习惯了， 时间不紧的题好像可以不用关同步。关同步反而限制了我用printf 和puts
代码
#include <bits/stdc++.h>
#ifndef ONLINE_JUDGE
#define debug(x) cout << #x << ": " << x << endl
#else
#define debug(x)
#endif
using namespace std;
typedef long long ll;
const int MAXN=2e5+;
const int INF=0x3f3f3f3f;
const int MOD=1e9+; void solve()
{
int n,x;
string s;
cin>>n>>x>>s;
int sum=;
for(int i=;i<s.size();++i)
{
if(s[i]=='') sum++;
else sum--;
}
int cur=,ans=;
if(x==) ans++;
for(int i=;i<s.size();++i)
{
if(s[i]=='') cur++;
else cur--;
if(!sum)
{
if(cur==x)
{
cout<<-<<endl;
return;
}
}
else if((x-cur)%sum== && (x-cur)/sum>=)
ans++;
}
cout<<ans<<endl;
}
int main()
{
ios::sync_with_stdio(false);
cin.tie();
int t;
cin>>t;
while(t--)
{
solve();
}
return ;
}
C.Obtain The String 思路就是记录每个字母依次出现的位置，然后对于目标串的每个字符去二分查找，更新位置信息，（这里我ans的更新和cur的位置写炸了，调了几十分钟。。。）
D.Same GCDs我眼中的欧拉函数裸题嘻嘻，数论专题没白做，C和D提交只差5min，zdnb。可惜赛后证明不来，只能口胡。。。
Jodran
The 2019 University of Jordan Collegiate Programming Contest
挺有趣的比赛哈哈，水题够多，也有有趣的题和idea.做了8题，补了E和J。
D.Robots Easy，一个机器人的，虽然我自己是疯狂特判模拟移动的，想起来好蠢，还写了好一会儿，思路没那么灵巧。
其实你不用动态更新维护当前的位置，1000次移动以内随便可以自己构造，保证他的启动位置到你的预设地点就行。
比如预设使得他到左下角，不停往左下移动即可，然后随便搞了。
E.Robots Hard ，四个机器人的，赛后补的，难度比上面那个大挺多，你要控制四个机器人同时移动，同时达到那四个目标点。
在模拟这个过程中，我感觉就在玩pokomon的滑冰或者水流圈，就是卡墙，卡间距和位置的感觉，嘻嘻。
建议还是自己手玩构造。我思路预设使得到左下角，成四个竖起来的。然后再卡。不太好描述，可以在原图上根据代码来画一下。
#include <bits/stdc++.h>
#ifndef ONLINE_JUDGE
#define debug(x) cout << #x << ": " << x << endl
#else
#define debug(x)
#endif
using namespace std;
typedef long long ll;
const int MAXN=2e5+;
const int INF=0x3f3f3f3f;
const int MOD=1e9+; int main()
{
ios::sync_with_stdio(false);
cin.tie();
string s;
for(int i=;i<;++i) s+="DL";
for(int i=;i<;++i)
{
s+="UUULLDDDLLL";
}
s+="UURRRRRRRRRRRRLLDDRULURRRRRRRDRRRRDLLUUUUU";
int n;
cin>>n;
while(n--)
{
int x;
cin>>x>>x>>x>>x>>x>>x>>x>>x;
cout<<s.size()<<endl;
cout<<s<<endl;
}
return ;
}
F.Arena Olympics ，视野夹角拓扑序，就要按视野夹角建图，在跑个拓扑排序输出顺序即可。主要是建图，我自己又if else 特判了情形。挺不错的题。
J.Zoo ，上海zoo...我对题面的理解有问题，导致做不了，一直玩不出第二个样例，主要是我一直认为 a->a+1->a画了三步，我数的是点数，那咋做的对。。。
然后可以递推计数，参看题解，毫无破绽的想法，dp[i][j]表示当前i路线的长度，j表示当前的sum，往前走则j+1，往后走则j-1，当前的状态由前一个长度的 j-1，j+1转移来。
最后求的是第二维为0的和。然后在把限制条件都加上。路线i最多到长度m，j最小为0（不能超出范围a）最多到min(i,k)，就结束了。 最后乘2n，n个位置，a的头尾选法。
贴个代码
#include <bits/stdc++.h>
#ifndef ONLINE_JUDGE
#define debug(x) cout << #x << ": " << x << endl
#else
#define debug(x)
#endif
using namespace std;
typedef long long ll;
const int MAXN=2e5+;
const int INF=0x3f3f3f3f;
const int mod=1e9+; ll dp[][];
//第一维表示路线长度 第二维表示当前和
int main()
{
ios::sync_with_stdio(false);
cin.tie();
int n,k,m;
cin>>n>>k>>m;
dp[][]=;
for(int i=;i<=m;++i)
{
for(int j=;j<=min(i,k);++j)
{
if(j) dp[i][j]=(dp[i-][j-] + dp[i-][j+])%mod;
else dp[i][j]=dp[i-][j+];
}
}
ll ans=;
for(int i=;i<=m;++i)
{
ans+=dp[i][];
ans%=mod;
}
ans*=*n;
ans%=mod;
cout<<ans<<endl;
return ;
}
K.Birthday Puzzle 基本都是2^n枚举子集水过，然后这题看题解由于或运算的特别性可以O(n)，准确来说是O(log(ai)*n)来做，非常优秀。
注意到或运算，只有当选出来的子集中，二进制这位上全部为0，才会没有这个位上的贡献，然后可以统计二进制为0的位的个数。
统计答案时，对于某个二进制位， （ n个数所有的子集个数 - 由这位上都是0的数组成的子集个数）*这位的权值
就结束了。
复杂度 2^n --> n 优化好大
然后其实 n大起来 一定是要对某个数取模的。。。就要用快速幂来算了。
#include <bits/stdc++.h>
#ifndef ONLINE_JUDGE
#define debug(x) cout << #x << ": " << x << endl
#else
#define debug(x)
#endif
using namespace std;
typedef long long ll;
const int MAXN=2e5+;
const int INF=0x3f3f3f3f;
const int MOD=1e9+; int a[MAXN];
int zero[];
int main()
{
ios::sync_with_stdio(false);
cin.tie();
int n;
cin>>n;
for(int i=;i<n;++i) cin>>a[i];
for(int i=;i<;++i)
{
for(int j=;j<n;++j)
{
if(!(a[j] & <<i))
zero[i]++;
}
}
ll ans=;
for(int i=;i<;++i)
ans+=(((1ll<<n)-)-((1ll<<zero[i])-))*(1ll<<i);
cout<<ans<<endl;
return ;
}
G线段树，F字符串构造 好像很难，我是不会补的~~~
结束了，逃