WORIA

http://codeforces.com/contest/1270/problem/E 题意：二维平面给出一些点，要求把这些点分成两组，任何不同组的两个点的欧式距离不能与任何同组的两个点的欧式距离相等。 奇偶分类构造 本题并不要求欧式距离估算出浮点数。例如 2\sqrt 22​ 不需要写成 1.414。所以欧式距离不同等价于欧式距离的平方不同，因此以下只讨论平方。 先把所有点分成4类，x，y分别为 {奇偶，偶奇，奇奇，偶偶}，则同一类的两个点欧式距离平方一定为偶数。对于不同组的，奇偶和偶奇，奇奇和偶偶也是偶数。所以只要把所有点各自分到四类中去，就自然组间距离为奇数，组内距离为偶数，也就不同了。 如果有3组或4组，可以直接按以上标准分类。 如果有2组，这两组组间距离可能还是偶数，但此时组间与组内距离绝对不同，因为组内是两个偶数的平方和，是4的倍数。组间是两个奇数的平方和，模4为2。所以直接把这两类分开即可。 如果只有1组，就把每个点坐标除以2，相当于距离都缩小了4，并不影响其是否相等，却可能改变其坐标的奇偶性，而产生新的分组。 由于奇数除2会有精度问题，所以在除2之前确 ...

不会用cb，调试C题的时候心态崩了，vs也太好用了，C题思路是对的，虽然会TL，但后来也是自己调好了；E题想到了按位建图，从高位开始跑，但想的是每次加点，觉得太麻烦，场上也没写，后来发现可以考虑删边，并且当时有细节也有问题；B题是真的不会，知道这游戏大概是先随便猜，再改，但具体是一点不会，也是第一道IO题。 A. 简单运算 单点时限: 1.0 sec 内存限制: 512 MB 在一行中从左到右写着 n 个数字 a1,a2⋯ana_1,a_2⋯a_na1​,a2​⋯an​ ，你需要在每相邻的两个数字间填入 + 或者 ^（异或）中的一个。 定义一种方案的权值为从左到右依次计算每个符号后得到的答案（即本题规定加法和异或的优先级相同），请你求出可以得到的最大的权值。 输入格式 第一行一个正整数 n(1≤n≤105)n ( 1≤n≤105 )n(1≤n≤105)。 第二行 n 个整数，表示 a1,a2⋯an(0≤ai≤105)a_1,a_2⋯a_n (0≤a_i≤105)a1​,a2​⋯an​(0≤ai​≤105)。 输出格式 输出一行一个整数表示答案。 样例 input 1221 2 ou ...

求cost−functioncost -functioncost−function： 二元分类 将每一个数据看作一个点。 设正确分类的概率为p(x). 实际得到的某点被分为1的概率为p(x|1), 则 若该点为1，则p(x)=p(x∣1),p(x)=p(x| 1),p(x)=p(x∣1), 若该点为-1，则p(x)=p(x∣−1)=1−p(x∣1)p(x)=p(x| -1)=1-p(x| 1)p(x)=p(x∣−1)=1−p(x∣1) 设F为给定点出现在指定位置且target function分类正确的概率 已知 f 为target function，即f始终为正确分类，f(x)==1 则对于f来说，产生给定分布的点集，且分类正确的概率 F=P(A)f(A)∗P(B)f(B)⋅⋅⋅=P(A)∗P(B)⋅⋅⋅F=P(A)f(A)*P(B)f(B) ···=P(A)*P(B)··· F=P(A)f(A)∗P(B)f(B)⋅⋅⋅=P(A)∗P(B)⋅⋅⋅ 即只与产生该分布情况的几率有关 再设H为给定点出现在指定位置且我的分类器分类正确的概率 设h为my function，则 ...

https://acm.ecnu.edu.cn/contest/255/ B. 与矩阵   题意：给定矩阵 AijA_{ij}Aij​ 表示 a[i]&a[j]a[i]\&a[j]a[i]&a[j] 的值，要求构造出字典序最小的 aaa 数列。 当 AijA_{ij}Aij​ 某一位为1时，a[i],a[j]a[i],a[j]a[i],a[j] 这一位都要为1，否则就当作为0，那么遍历每个 jjj ，确定 a[i]a[i]a[i] 即可。 1234567891011121314151617181920212223242526#include<bits/stdc++.h>using namespace std;#define ll long longconst int N = 3e5 + 10;const int INF = 0x3f3f3f3f;int n;int a[1010][1010];int sum[1010];int main() { scanf("%d", &n); for (int i = 1; i ...

https://acm.ecnu.edu.cn/contest/448/ E. Effective Gradient   题意：给定 p,qp, qp,q，以及平面上 nnn 个点，求一条至少过两个点的直线，斜率与 p/qp / qp/q 的差的绝对值最小。 几何 把所有点按照与直线 y=pqxy=\frac{p}{q}xy=qp​x 的有向距离的大小排序。即按照 pqxi−yi\frac{p}{q}x_i-y_iqp​xi​−yi​ 排序。 最终答案的两个点一定相邻。否则选择它们中间的一个点，一定与这两点之一能够组成更优的直线。 之所以是有向距离是因为在直线两侧的点不同。 123456789101112131415161718192021222324252627282930313233343536373839404142434445#include<bits/stdc++.h>using namespace std;#define ll long longconst int INF = 0x3f3f3f3f;const int N = 2e6 + 10;const ll ...

https://acm.ecnu.edu.cn/contest/375/ D. 关于小方的爆款桌游还没面世就要夭折这回事   题意：n*m的棋盘，n 为偶数，每个棋子 1*2，可以横着或竖着放，无法落子的输，问先手胜负。 博弈 考虑模仿对手。 若 m 为偶数，则后手始终放在与先手中心对称的位置，则后手必胜。 若 m 为奇数，则先手放在最中心处，之后始终模仿后手，则先手必胜。 12345678910111213141516171819#include <bits/stdc++.h>#define debug(x) cout << #x << ":\t" << (x) << endl;using namespace std;#define ll long long#define ull unsigned llconst int N = 2e6 + 10;const int INF = 0x3f3f3f3f;const ll inf = 0x3f3f3f3f3f3f3f3f;const ll mod = 1e9 ...

http://codeforces.com/contest/1437 E. Make It Increasing   题意：给定数列 A 和 B ，每次操作任选 A 中一个数，修改成任意值，但是下标在 B 中的数不能改。问最少操作次数使得 A 严格递增。 树状数组 B 数组把 A 数组分成几块，对于每块单独处理。 两个数能够递增等价于 ai−aj≥i−ja_i-a_j\ge i-jai​−aj​≥i−j，也就是 ai−i≥aj−ja_i-i\ge a_j-jai​−i≥aj​−j。 所以要求最长非递减子序列。 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960#include <bits/stdc++.h>#define debug(x) cout << #x << ":\t" << (x) << endl;using namespace ...

https://codeforces.com/contest/1400 E. Clear the Multiset 题意：给定 n 个数，两种操作：任选一个区间，区间中所有数 -1；任选一个数，这个数减去任意值。不能出现负数。问最少操作次数使得所有数变为 0。 分治 由于不能出现负数，所以对于某个区间，第一种操作最多进行次数为该区间最小值。操作后该区间分裂为两个区间，再各自进行操作。 以最小值点 p 为分割点，分治左右区间。分裂的代价有两种：操作一进行多次，或直接进行一次操作二。这两种方式得到左右区间的不同之处在于：第一种方式会使得所有数减去最小值。需要记录下来最终结果为两者取最小值。即 min(dfs(l,p−1,−a[p])+dfs(p+1,r,−a[p])+a[p]+ad,dfs(l,p−1,ad)+dfs(p+1,r,ad)+1)min(dfs(l,p-1,-a[p])+dfs(p+1,r,-a[p])+a[p]+ad,dfs(l,p-1,ad)+dfs(p+1,r,ad)+1)min(dfs(l,p−1,−a[p])+dfs(p+1,r,−a[p])+a[p]+ad,dfs( ...

http://codeforces.com/contest/1398 E. Two Types of Spells   题意：两种咒语：fire可以造成 did_idi​ 伤害，lightning可以造成 did_idi​ 伤害并且使下一个咒语伤害翻倍。初始咒语集合为空，n 次，每次向集合中添加或删除一个fire或lightning，问每次修改后用集合中咒语最多造成的伤害。 模拟 策略还是比较直接的：假设集合中有 c1 个lightning，则把前 c1 大个咒语翻倍。但是要注意如果前 c1 个包含了所有lightning，则无法全部翻倍，必须放弃一个最小的lightning，再另选一个。 维护两个set，第一个维护前c1大的咒语，第二个维护剩下的。 每次操作后需要更新这两个set，此时先不考虑“lightning不能全翻倍”这一限制，在取答案时再考虑。就类似维护堆，如果插入一个数，判断如果这个数大于第一个set中最小的，则它会代替最小的，所以要把这个数插入第一个set；否则插入第二个。再根据新的c1值，删除或增加set。 要注意并不是直接插到第二个set里就好了，必须判断能否插入第一 ...

https://codeforces.com/contest/1373 E. Sum of Digits   题意：给定n，k，问最小的x，满足 f(x)+f(x+1)+⋯+f(x+k)=nf(x) + f(x + 1) + \dots + f(x + k) = nf(x)+f(x+1)+⋯+f(x+k)=n，其中 f(x)f(x)f(x) 为 x 的各位数字和。1≤n≤150,0≤k≤91 \le n \le 150,0 \le k \le 91≤n≤150,0≤k≤9 贪心 由给定数据范围可知 x 最多进位一次。 枚举x的位数和最高位，对于每一种位数和最高位，只需要枚举后20个数。 对于任意一个数（位数足够多），一定可以变成次低位为8或9的数，且保持和不变，例如 479，可以变成 389。 且不能再缩小范围了，因为次低位小于8的可以变成8，但是次低位为8的和次低位为9的可能k个数和不同，因为9有进位。 而需要枚举最高位则是因为防止由于总和不够而增加位数。 1234567891011121314151617181920212223242526272829303132333435363 ...