Day5
T1
赛时写了三个点终于写出来了
好的三元组定义为
\[P = a_i \times 2 ^ {\lfloor log_2^{a_j} \rfloor + 1 + \lfloor log_2^{a_k} \rfloor + 1} + a_j \times 2^{\lfloor log_2^{a_k} \rfloor + 1} + a_k
\]
其中对于
\[2 ^ {\lfloor log_2^{a_j} \rfloor + 1}
\]
可以令
\[b_j = 2 ^ {\lfloor log_2^{a_j} \rfloor + 1}
\]
然后式子就化为了
\[P = a_i \times b_j \times b_k + a_j \times b_k + a_k
\]
可得
\[\frac{P - a_k}{b_k} = a_i \times b_j + a_j
\]
记 \(V = \frac{P - a_k}{b_k}\)
因等式右边必定为整数， 则\((P - a_k) \mod b_k = 0\)
则我们可以预先算出所有可能作为 \(a_k\) 的值
由于 \(b_k\) 必定为 \(2\) 的幂次， 而 \(P <= 2 ^ {60}\) 则 \(a_k\) 的值最多有六十种
从头遍历存下来，再顺便存下每种 \(a_k\) 的个数， 用 \(map\) 方便多测清空
然后我们从头开始枚举 \(j\)
- 每次枚举时再记一下每个数目前的出现次数 \(pre_{a_i}\) 开个 \(map\) 方便多测清空
- 然后枚举所有可能的 \(a_k\) ，由 \(\frac{P - a_k}{b_k} = a_i \times b_j + a_j\) 可得 \(\frac{\frac{P - a_k}{b_k} - a_j}{b_j} = a_i\)
- 则 \((V - a_j) \mod b_j = 0\)
- 然后我们可以计算出需要的 \(a_i = \frac{V - a_j}{b_j}\)
- \(a_i, a_k已知\)， 通过 \(pre\) 数组可计算出相应个数
Code:
#include <bits/stdc++.h>
#define ll long long
#define gt getchar
#define pt putchar
using namespace std;
inline ll read(){
ll x=0,f=1;char ch=gt();
while(!isdigit(ch)){if(ch=='-')f=-1;ch=gt();}
while(isdigit(ch)){x=(x<<1)+(x<<3)+(ch^48);ch=gt();}
return x*f;}
inline void print(ll x){if(x<0)pt('-'),x=-x;if(x>9)print(x/10);pt(x%10+48);}
void file(){freopen("equation_sample2.in", "r", stdin);}
int n;
ll p;
const int maxn = 100005;
int a[maxn], b[maxn];
int tot = 0, ck[maxn];
map<int, int> cnt;
inline int ksm(int a, int b)
{
int res = 1;
while(b)
{
if(b & 1)res = res * a;
a = a * a;
b >>= 1;
}
return res;
}
map<int, int> pre;
void work()
{
tot = 0;
cnt.clear(), pre.clear();
n = read(), p = read();
for(int i = 1; i <= n; ++ i)
{
a[i] = read(), b[i] = ksm(2, 1 + int(log2(double(a[i]))));
if(((p - a[i]) % b[i]) == 0)//所有可能成为a_k的数
{
if(cnt[a[i]] == 0)ck[++ tot] = i;
++ cnt[a[i]];
}
}
ll ans = 0;
for(int i = 1; i <= n; ++ i)
{
++ pre[a[i]];
for(int j = 1; j <= tot; ++ j)//枚举a_k取值
{
ll v = (p - a[ck[j]]) / b[ck[j]];
ll tim = cnt[a[ck[j]]] - pre[a[ck[j]]];
if((v - a[i]) % b[i] == 0)
{
if(a[i] == ((v - a[i]) / b[i]))ans -= tim;
ans += pre[(v - a[i]) / b[i]] * tim;
}
}
}
print(ans);
pt('\n');
}
int main()
{
//file();
int T = read();
while(T--)
{
work();
}
return 0;
}
T2
每次删除一个操作，终点只可能有四种变化情况
枚举四个终点，倒推路径
枚举删除的操作，删除相应路径中起点，加入一个新的点 \(map\) 维护
#include <bits/stdc++.h>
#define ll long long
#define pii pair<int, int>
#define gt getchar
#define pt putchar
using namespace std;
inline ll read(){
ll x=0,f=1;char ch=gt();
while(!isdigit(ch)){if(ch=='-')f=-1;ch=gt();}
while(isdigit(ch)){x=(x<<1)+(x<<3)+(ch^48);ch=gt();}
return x*f;}
inline void print(ll x){if(x<0)pt('-'),x=-x;if(x>9)print(x/10);pt(x%10+48);}
void file(){freopen("equation_sample2.in", "r", stdin);}
const int maxn = 300005;
int n;
map <pii, int> mp, mp1;
char s[maxn];
void move(int &x, int &y, int v)
{
if (s[v] == 'L') -- x;
if (s[v] == 'R') ++ x;
if (s[v] == 'D') -- y;
if (s[v] == 'U') ++ y;
}
void rmove(int &x, int &y, int v)
{
if (s[v] == 'R') -- x;
if (s[v] == 'L') ++ x;
if (s[v] == 'U') -- y;
if (s[v] == 'D') ++ y;
}
ll res = 0;
void add(int x, int y)
{
++ mp[{x, y}];
res += mp[{x, y}] * ((abs(x) + 1) ^ (abs(y) + 1)) + mp[{x, y}];
}
void del(int x, int y)
{
res -= (mp[{x, y}] * ((abs(x) + 1) ^ (abs(y) + 1)) + mp[{x, y}]);
-- mp[{x, y}];
}
ll ans[maxn];
int main() {
n = read();
scanf("%s", s + 1);
int x = 0, y = 0;
add(x, y);
for (int i = 1; i <= n; ++ i)
{
move(x, y, i);
add(x, y);
}
int st = x, ed = y;
char tar;
int nx, ny;
ll sum = res;
mp1 = mp;
for (int i = 0; i < 4; ++ i)
{
if (i == 0) nx = st + 1, ny = ed, tar = 'L';
if (i == 1) nx = st - 1, ny = ed, tar = 'R';
if (i == 2) nx = st, ny = ed + 1, tar = 'D';
if (i == 3) nx = st, ny = ed - 1, tar = 'U';
res = sum;
x = st, y = ed;
del(x, y);
rmove(x, y, n);
for (int j = n; j >= 1; j--) {
if (s[j] == tar) ans[j] = res;
del(x, y);
if (j != 1) rmove(x, y, j - 1);
add(nx, ny);
rmove(nx, ny, j);
}
mp = mp1;
}
for (int i = 1; i <= n; i++) cout << ans[i] << '\n';
return 0;87}
T3
#include <bits/stdc++.h>
#define ll long long
#define gt getchar
#define pt putchar
using namespace std;
inline ll read(){
ll x=0,f=1;char ch=gt();
while(!isdigit(ch)){if(ch=='-')f=-1;ch=gt();}
while(isdigit(ch)){x=(x<<1)+(x<<3)+(ch^48);ch=gt();}
return x*f;}
inline void print(ll x){if(x<0)pt('-'),x=-x;if(x>9)print(x/10);pt(x%10+48);}
void file(){freopen(".in", "r", stdin);freopen(".out", "w", stdout);}
ll n, m, k, a[205];
const int maxn = 200005;
int main()
{
//file();
int T = read();
while(T--)
{
n = read(), m = read(), k = read();
for(int i = 1; i <= k; ++ i)a[i] = read();
bitset<maxn> f;
f[0] = 1;
for(int i = 0; i < 60; ++ i)
{
if(n >> i & 1)
{
bitset<maxn> g;
for(int j = 1; j <= k; ++ j)g ^= f << a[j];
f = g;
}
bitset<maxn> g;
for(size_t j = m >> i & 1; j < f.size(); j += 2)g[j >> 1] = f[j];
f = g;
}
cout << f[0] << '\n';
}
return 0;
}