B - Traveling Salesman Problem
给一个分子是奇数，分母是2的幂次的真分数，要用两种操作把它从1构造出来。
一种是除以2，另一种是求对1的补数。
画了一下手模觉得每个位只能有一次机会被构造。（除非连续求几次补数这种**行为）。
类似快速幂这样分解的时候要记得把0也弄上不然就直接死循环T了。
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
string trans(ll a) {
string sa;
while(a) {
//cout<<"a="<<a<<endl;
if(a & 1)
sa = '1' + sa;
else
sa = '0' + sa;
a >>= 1;
}
return sa;
}
int main() {
#ifdef Yinku
freopen("Yinku.in", "r", stdin);
#endif // Yinku
ll a, b;
while(cin >> a >> b) {
string sa, sb;
sb += '1';
ll cb = 1;
while(b) {
cb <<= 1;
sb += '0';
b--;
}
ll ca = a;
while(a) {
if(a & 1)
sa = '1' + sa;
else
sa = '0' + sa;
a >>= 1;
}
//cout << sa << "/" << sb << endl;
//cout << ca << "/" << cb << endl << endl;
string ans;
while(sb.size() > 1) {
if(ca != 1 && (sa.size() == sb.size() - 1)) {
ans = '1' + ans;
ca = cb - ca;
sa = trans(ca);
} else {
cb >>= 1;
sb = sb.substr(0, sb.size() - 1);
ans = '0' + ans;
}
//cout << sa << "/" << sb << endl;
//cout << ca << "/" << cb << endl << endl;
}
cout << ans << endl;
}
}
题意，给一串带问号的数字，要你把问号换成数字，把n构造成k的最小的倍数，并且n不能有前导零。
这个超级坑爹，输入自己有前导零的，有毒。
一开始想了很久不知道怎么搞，觉得看起来像以前的数位dp，只不过这个不是问[l,r]之间的数的数量，不需要考虑什么上界的限制，只需要确定余数。
从最低位开始数位dp的话，不知道是怎么样才能构造最小，所以只能够从最高位开始构造，这样就蛮麻烦的。
用类似bool数组的办法来记录每个余数种类的可行性。每次最高位的dp值保存两个信息，首先是它的上一步是谁（用来复原方案），然后就是它这一路选过的数字的大小在这一层里面的名次（用来贪心转移到下一层）。
最后回答答案的时候，要注意是要减去每个位的值，因为存的余数是“从最高位开始的前缀和”，当然是要反过来减掉。
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
char s[1005];
char dp[1005][10][1005];
int qpow(int x, int n, int m) {
int res = 1;
while(n) {
if(n & 1)
res = res * x % m;
x = x * x % m;
n >>= 1;
}
return res;
}
int pow10[1005];
typedef pair<int, pair<int, int> > pii;
pii p[2][100005];
int ptop[2];
int ans[1005];
int main() {
#ifdef Yinku
freopen("Yinku.in", "r", stdin);
#endif // Yinku
int n, k;
while(~scanf("%d%d", &n, &k)) {
scanf("%s", s + 1);
if(n == 1) {
if(s[1] == '?')
puts("0");
else {
int x = s[1] - '0';
if(x % k == 0)
puts(s + 1);
else
puts("-1");
}
continue;
}
if(s[1] == '0') {
puts("-1");
continue;
}
pow10[0] = 1;
for(int i = 1; i <= n; ++i) {
pow10[i] = pow10[i - 1] * 10 % k;
}
memset(dp, -1, sizeof(dp));
ptop[1] = 0;
if(s[1] != '?') {
int curj = s[1] - '0';
int curk = pow10[n - 1] * curj % k;
dp[1][curj][curk] = 10;
p[1][++ptop[1]] = {10, make_pair(curj, curk)};
} else {
for(int curj = 1; curj <= 9; ++curj) {
int curk = pow10[n - 1] * curj % k;
dp[1][curj][curk] = 10;
p[1][++ptop[1]] = {10, make_pair(curj, curk)};
}
}
for(int i = 2; i <= n; ++i) {
int cntl = 0;
register int pre = (i - 1) & 1, cur = (i & 1);
ptop[cur] = 0;
sort(p[pre] + 1, p[pre] + 1 + ptop[pre]);
if(s[i] != '?') {
int curj = s[i] - '0';
for(int pj = 1; pj <= ptop[pre]; ++pj) {
int prej = p[pre][pj].second.first;
int prek = p[pre][pj].second.second;
int curk = (prek + pow10[n - i] * curj) % k;
if(dp[i][curj][curk] == -1) {
dp[i][curj][curk] = prej;
p[cur][++ptop[cur]] = {++cntl, make_pair(curj, curk)};
}
}
} else {
for(int pj = 1; pj <= ptop[pre]; ++pj) {
for(int curj = 0; curj <= 9; ++curj) {
int prej = p[pre][pj].second.first;
int prek = p[pre][pj].second.second;
int curk = (prek + pow10[n - i] * curj) % k;
if(dp[i][curj][curk] == -1) {
dp[i][curj][curk] = prej;
p[cur][++ptop[cur]] = {++cntl, make_pair(curj, curk)};
}
}
}
}
}
register int cur = (n & 1);
sort(p[cur] + 1, p[cur] + 1 + ptop[cur]);
int res = -1;
for(int pj = 1; pj <= ptop[cur]; ++pj) {
int curj = p[cur][pj].second.first;
int curk = p[cur][pj].second.second;
if(curk == 0) {
res = curj;
break;
}
}
if(res != -1) {
int curj = res, newj = -1;
int curk = 0, newk = -1;
for(int i = n; i >= 1; --i) {
ans[i] = curj;
newj = dp[i][curj][curk];
newk = ((curk - pow10[n - i] * curj) % k + k) % k;
curj = newj;
curk = newk;
}
for(int i = 1; i <= n; ++i)
printf("%d", ans[i]);
printf("
");
} else
puts("-1");
}
}
有毒，明明是有序对，又给我说无序，真的有毒。
要求所有有序三元组的异或和的和，考虑到每个位实际上是独立的，只考虑单独的某位k，那么它的贡献值就是它的值乘上使它为1的组合，那么就只有(1,1,1)和(0,0,1)两种咯，分别统计一下就可以了。
不知道有没有处理部分O(1)的办法，反正这样肯定可以。感觉是有的，(1,1,1)的那种直接cnt1立方就行，然后(0,0,1)这样的，排一下就是3(cnt0)(cnt0)*(cnt1)，非常简单。不过不用动脑是最好的。
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int n;
int a[10005];
int cnt[2][21];
int main() {
#ifdef Yinku
freopen("Yinku.in", "r", stdin);
#endif // Yinku
int n;
while(~scanf("%d", &n)) {
memset(cnt, 0, sizeof(cnt));
for(int i = 1; i <= n; ++i) {
scanf("%d", &a[i]);
for(int k = 0; k <= 20; ++k)
++cnt[(a[i] >> k) & 1][k];
}
ll sum = 0;
for(int i = 1; i <= n; ++i) {
for(int k = 0; k <= 20; ++k) {
if((a[i] >> k) & 1) {
sum += (1ll << k) * (cnt[0][k] * cnt[0][k]);
sum += (1ll << k) * (cnt[1][k] * cnt[1][k]);
} else {
sum += (1ll << k) * (cnt[0][k] * cnt[1][k]);
sum += (1ll << k) * (cnt[1][k] * cnt[0][k]);
}
}
}
printf("%lld
", sum);
}
}