FALSE OR TRUE
给你一个平面上N个点组成的环, 现在要你连M条边, 每条边链接环上两个点, 问能否有一种方案连边使得边不相交。
解题报告
抖机灵题目, 如果对于边(a, b)和(c, d) (保证a<b并且c<d)有a<c<b<d, 那么边(a, b)和边(c, d)冲突, 这意味着两条边不能在环的同一边, 否然会相交。
把边看成点, 冲突关系看成边, 问题转化为判断这个图是否可以被二染色, dfs即可。
这个傻逼题忘记清零害的我卡了几个小时…无力…
Nescafe18-七夕祭
给你一个N*M的网格, 其中有T个格子染成黑色(其余白色), 现在问能否通过交换相邻格子使得每行黑色格子数量相等或且每行白色格子数量相等或同时满足两者。如果能, 问最小交换次数。
注意相邻定义为边相邻, 同时每一行的第一个格子和这一行的最后一个格子相邻, 每一列第一个格子和这一列最后一个格子相邻。
[latex]N, M \le 100000, T \le min(100000, N \times M)[/latex]
解题报告
考试的时候以为想到了正解…然而是假的
首先观察发现’交换’并没有卵用, 如果交换黑色格子和白色格子, 那么相当于移动黑色格子。如果交换黑色格子和黑色格子, 那么一定不优(因为交换完毕后状态完全一样)。
接着发现行和列是完全互相独立的, 不加赘述。
那么问题就转化成在两个环上了。
对于一个环, 我们的目标是让这个环上每个节点内的黑色格子数量一样多(数量都为lim), 每个黑色格子可以向左或这向右移动, 移动一次的代价为1, 要求总代价最小。
现在假设环上有N个节点, 第N个节点移动个第1个节点a个黑色格子, 初始第i个节点黑色格子数量与lim的差值为
cnt[i]
, 第i个节点移动给下一个节点的黑色格子数量为
mov[i]
(负数代表反向移动), 并且设
sum[i]
为
cnt
的前缀和, 那么有如下关系:
$$ mov[1] = cnt[1]+a $$
$$ mov[2] = cnt[2]+mov[1] = cnt[2]+cnt[1]+a $$
$$ mov[i] = \sum_{j=1}^i cnt[j] +a = sum[i]+a $$
答案
ans
等于
|mov|
之和, 就有:
$$ ans = \sum_{i=1}^N |mov[i]| = \sum_{i=1}^N |sum[i]+a| = \sum_{i=1}^N |sum[i]-(-a)|$$
a可以等于mov中的任意一个值, 问题转化成一个数轴上有一堆点, 选择一个点使得所有点到这个点的距离和最小。
明显就要选取中位数了, 问题解决。
Nescafe18-理科男
给你一个分数[latex]\frac{A}{B}[/latex], 问这个分数在K进制下是有限不循环小数或者有限循环小数, 并且求出循环串长度和不循环串长度。
[latex]A<B,K \le 10^12[/latex]
解题报告
把A/B约分后进行操作。
首先, 设X为A/B, 那么X可以表示为:
$$ X = \frac{a}{K^1}+\frac{b}{K^2}+… $$
如果对B和K进行质因数分解:
$$ B = {a_1} ^ {p_1} + {a_2} ^ {p_2} + … + {a_x}^{p_x}, K = {b_1} ^ {q_1} + {b_2} ^ {q_2} + … + {b_x}^{q_x} $$
那么如果B的因子都在K的因子中出现过了, 那么X必然能够在有限位内被表示出来, 这里证明不加赘述, 有限小数数位为
max(ceil(p
i
/q
j
)}
, 其中p
i
等于q
j
。
把B中能够被K消掉的因子去掉后, 用新的B继续进行循环小数方面的处理。
我们发现X乘上任意实数的话, 小数循环节长度不会改变, 所以利用这个性质可以把现在的分子看成是1。
假设循环节长度为M, 循环为R, 那么有如下规律:
$$ 0.\overline{R}\overline{R}\overline{R}… \times K^M = R + 0.\overline{R}\overline{R}\overline{R}… $$
变形一波:
$$ \frac{R}{K^M-1} = 0.\overline{R}\overline{R}\overline{R}… = \frac{1}{B}$$
$$ K^M-1= BR \Rightarrow K^M \equiv 1 \pmod B $$
K和B在去掉公共因子后显然互质, 根据欧拉定理:[latex] K^{\varphi(B)} \equiv 1 \pmod B [/latex]
要求得M最小, 所以[latex] M | \varphi(B) [/latex], 枚举B的因子即可, 复杂度根号乘log。
写不清楚的看代码吧…
代码
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <climits>
#include <cstdlib>
#include <vector>
#include <cmath>
using namespace std;
typedef long long LL;
vector<pair<LL, int> > facB, facK, seq;
LL gcd(LL a, LL b) {return b?gcd(b, a%b):a;}
LL lcm(LL a, LL b) {return a/gcd(a, b)*b;}
inline LL mul (LL a, LL b, LL m) {
LL cur = a%m, ret = 0;
while(b) {
if(b&1) ret = (ret+cur)%m;
cur = (cur+cur)%m;
b >>= 1;
}
return ret;
}
inline LL advPow (LL a, LL b, LL m) {
LL ret = 1;
while(b) {
if(b&1) ret = mul(ret, a, m);
a = mul(a, a, m);
b >>= 1;
}
return ret;
}
void resolve (LL num, vector<pair<LL, int> > & vec) {
vec.clear();
for(LL i = 2; i*i <= num; i++) {
if(num%i == 0) {
int cnt = 0;
while(num%i == 0) num /= i, cnt ++;
vec.push_back(pair<LL, int>(i, cnt));
}
}
if(num != 1) vec.push_back(pair<LL, int>(num, 1));
}
LL eularFunc (LL val) {
LL ret = 1;
for(LL i = 2; i*i<=val; i++ ) {
if(val % i != 0) continue ;
ret *= i-1, val /= i;
while(val%i == 0) val /= i, ret *= i;
}
if(val != 1) ret *= val-1;
return ret;
}
LL A, B, K, nB;
inline bool check (LL M) {
//printf("chk:%lld\n", M);
return advPow(K, M, nB) == 1;
}
int main () {
freopen("kubi.in", "r", stdin);
freopen("kubi.out", "w", stdout);
int T;
scanf("%d", &T);
while(T --) {
LL tmp;
scanf("%lld%lld%lld", &A, &B, &K);
tmp = gcd(A, B);
A /= tmp, B /= tmp;
resolve(B, facB);
resolve(K, facK);
int mxv = 0, cur = 0;
bool flg = false;
nB = B;
for(int i = 0; i<(int)facB.size(); i++) {
while(cur < (int)facK.size() && facK[cur].first < facB[i].first) cur ++;
if(cur == (int)facK.size() || facK[cur].first != facB[i].first) flg = true;
else mxv = max(mxv, (int)ceil((double)facB[i].second/facK[cur].second)),
nB /= advPow(facB[i].first, facB[i].second, 0x3f3f3f3f3f3f3f3fLL);
}
if(!flg) {printf("%d 0\n", mxv); continue ;}
LL phi = eularFunc(nB), ans = phi;
for(LL i = 1; i*i <= phi; i++) {
if(phi%i != 0) continue ;
if(check(i)) ans = min(ans, i);
if(check(phi/i)) ans = min(ans, phi/i);
}
printf("%d %lld\n", mxv, ans);
}
}
SET
给定三个正整数 l , r , k ,构造一个整数集合 S 满足以下条件:
1. 对于 S 中的每个元素 x ,均有 [latex]l \le x \le r[/latex] 。
2. [latex]1 \le |S| \le k [/latex]
3. 集合 S 中所有数的二进制按位异或后的结果尽可能小。
你需要输出这个集合。
数据范围:
一共有T组测试数据(T最大为10000)。
对于每一组数据, [latex]1 \le l,r \le 10^{12}, 1 \le k \le r-l+1[/latex]
对于所有数据, [latex]\sum k \le 10^6[/latex]。
解题报告
诡异的CF题目,
传送链接
。
我们来慢慢挖掘性质:
1. k大于等于4
考虑k大于等于4的情况, 我们是否能够选取4个数字就让异或值达到0呢?
答案是肯定的, 而且只需要选择连续的4个数字, 这样它们分别为:
xxxx00, xxxx01, xxxx10, xxxx11
注意’
xxxx
‘部分异或值一定是0(偶数个), 后面’
00, 01, 10, 11
‘异或起来也是0, 答案不可能更优了。
所以, 当k大于等于4时, 若区间长度大于等于7, 根据鸽笼原理, 一定可以构造一个异或和为0的集合!
如果区间长度小于7怎么办呢? 注意到可选择的元素只剩下不多于6个了, 暴力二进制枚举即可。
这样, k大于等于4的情况就能够使用上面方法解决了。
2. k等于1
显然…能且只能选一个l。
3. k等于2
k等于2, 答案明显不可能等于0, 因为只有当两个元素相同时异或值才为0。
那么答案可能等于1么?
考虑选取两个如下的相邻数字:
xxxx0, xxxx1
异或和为1, 达到最优, 类似第一种情况, 当区间长度大于等于3时, 必然存在这样的一对连续数字。
当区间长度小于3时, 暴力枚举三种情况即可。
4. k等于3
这是最复杂的一种情况。
首先, k等于3的最优异或和至少为1, 因为一定可以从区间内选择两个相邻数使得异或和为1(区间长度大于等于3, 第三种讨论已经指出)。
异或和有没有可能等于0呢? 答案是肯定的, 比如:
7: 111
4: 100
3: 011
异或和: 0
那么是不是较小两个数相加就等与最大的数字呢? 不一定。
6: 110
5: 101
3: 011
异或和: 0
我们假设这三个数字从大到小分别为a, b, c。
发现三个数字中二进制下每一位都必然出现恰好两个’1′, 那么a和b的最高位必然同为1, c的最高位为0, 我们用对数级时间可以枚举这三个数字的最高位是第几位.
如果数据给出区间[l, r]包含了区间[c, a], 那么可以构造出异或和为0的答案。
a异或b等于c, 显然在a固定时, c要尽量大。
由于c的最高位一定为0, 理想的c能够达到01111…, 但是由于上节r的限制, a异或b不一定能够达到01111….。
(1). 如果r的二进制表示最高位大于了当前枚举的最高位, 那么c可以达到理想的01111…, 因为此时a的取值可以为111111…, b取100000…。
(2). 假如r的二进制表示最高位等于当前枚举的最高位, r=100..001xxxxx.., 那么a和b异或起来可以达到000..001111111…, 这个显然。接下来要最小化a, 理想的a一定是100..001000…(r中第一个和第二个1所在位置为1), 那么b就是100..000111…(异或起来等于r), 显然没有比此更优的方案了。
(3). r的二进制表示最高位小于当前枚举的最高位, a和b一定都大于r, 直接放弃。
问题解决。
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <climits>
#include <cstdlib>
#include <vector>
using namespace std;
typedef long long LL;
vector<LL> ans, seq;
int high1 (LL num) {
LL cnt = 0, lvl = 1;
while(num >= lvl) lvl<<= 1, cnt++;
return cnt;
}
int main () {
int T;
scanf("%d", &T);
while(T --) {
LL l, r, k;
ans.clear();
scanf("%I64d%I64d%I64d", &l, &r, &k);
if(k == 1) ans.push_back(l);
else if(k == 2) {
if(r-l+1 == 2) {
if((l^r) < l) ans.push_back(l), ans.push_back(l+1);
else ans.push_back(l);
} else {
if(l&1) l++;
ans.push_back(l), ans.push_back(l+1);
}
} else if(k == 3) {
bool flg = false;
for(LL i = 1; i<=r; i<<=1)
if(i >= l) {
LL delt = (1LL<<high1(r-i))-1;
LL range = min(i-1, delt);
if(l <= range) {
flg = true;
if(i-1 >= delt) {
ans.push_back(i+(1LL<<(high1(r-i)-1)));
ans.push_back(i+(1LL<<(high1(r-i)-1))-1);
ans.push_back(range);
} else {
ans.push_back(i+i-1);
ans.push_back(i);
ans.push_back(i-1);
}
break;
}
}
if(!flg) {
if(l&1) l++;
ans.push_back(l), ans.push_back(l+1);
}
} else {
if(r-l+1 >= 7) {
for(; l&3; l++) ;
ans.push_back(l);
ans.push_back(l+1);
ans.push_back(l+2);
ans.push_back(l+3);
} else {
seq.clear();
for(LL i = l; i<=r; i++)
seq.push_back(i);
int len = r-l;
int lim = 1<<(r-l+1);
LL cans = 0x3f3f3f3f3f3f3f3fLL, cur, rec;
for(int s = 1; s<lim; s++) {
cur = 0;
for(int i = 0; i<=len; i++)
if(s&(1<<i)) cur ^= seq[i];
if(cur < cans) cans = cur, rec = s;
}
for(int i = 0; i<=len; i++)
if(rec&(1<<i)) ans.push_back(seq[i]);
}
}
LL val = 0;
for(int i = 0; i<(int)ans.size(); i++)
val ^= ans[i];
printf("%I64d\n%d\n", val, ans.size());
std :: sort(ans.begin(), ans.end());
for(int i = 0; i<(int)ans.size(); i++)
printf("%I64d%c", ans[i], (i == (int)ans.size()-1) ? '\n' : ' ');
}
}
SUBGRAPH
给定一张无向图G( V , E ) , 每个点都有一个非负整数点权w
i
, 并且满足如下条件:
1. 所有的点分为两类。
2. 第一类的两个不同的点u, v之间有连边当且仅当(w
u
xor w
v
) mod 2 = 1 。
3. 第二类的两个不同的点u, v之间有连边当且仅当(w
u
xor w
v
) mod 2 = 0 ,
或者 ( w
u
or w
v
)在二进制表示下有奇数个1。
4. 第一类的点和第二类的点之间有可能连边,这个连边关系在输入数据中给出, 两类点之间不会有重边。
定义一个图的子图 G'( V ‘,E’) , 满足 V ‘ 属于 V , 且对于任意一条边(u, v)属于E ‘, 均有u属于V且v属于V 。
现在你的任务就是找一个原图G( V , E )的子图G'( V ‘, E’), 使得G’是完全图,并且|V’|尽可能大, 只需输出最大的|V’|即可。
解题报告
留个坑…提醒自己去填…
Join the discussion