T1.涂色游戏（paint）
可以按照题意模拟，每一次暴力对于每一行列染色，时间复杂度 \(O(qn)\)。可得60pts。
因为颜色可以覆盖，某一格的颜色往往取决于最后一次被染到的颜色。
于是我们采用打标记的方式。每一次染色（行或列）就在当前行列打标记，记操作时间戳 \(t\)。
最后输出答案时枚举每一格，比较当前行列的时间戳 \(t\)，\(t\) 更大的标记对应的颜色就是覆盖的颜色。
时间复杂度 \(O(q+nm)\)，100pts。
点击查看代码
#include<bits/stdc++.h>
#define int long long
#define rint register int
#define For(i,l,r) for(rint i=l;i<=r;++i)
#define FOR(i,r,l) for(rint i=r;i>=l;--i)
using namespace std;
inline int read() {
rint x=0,f=1;char ch=getchar();
while(ch<'0'||ch>'9'){if (ch=='-') f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}
return x*f;
}
const int N = 1e6 + 5;
struct Node {
int id, c;
} Ansh[N], Ansl[N];
int n, m, T, q;
void init() {
For(i,1,n) {
For(j,1,m) {
Ansh[i] = (Node) {0, 0};
Ansl[j] = (Node) {0, 0};
}
}
}
signed main() {
T = read();
while(T--) {
n = read(), m = read(), q = read();
init();
For(l,1,q) {
int op = read(), x = read(), c = read();
if(op == 0) {
Ansh[x] = (Node) {l, c};
} else {
Ansl[x] = (Node) {l, c};
}
}
For(i,1,n) {
For(j,1,m) {
if(j != m) {
if(Ansh[i].id > Ansl[j].id) {
cout << Ansh[i].c << ' ';
} else {
cout << Ansl[j].c << ' ';
}
}
else {
if(Ansh[i].id > Ansl[j].id) {
cout << Ansh[i].c;
} else {
cout << Ansl[j].c;
}
}
}
cout << endl;
}
}
return 0;
}
T2.幂次（power）
- \(k=1\)
答案显然就是 \(n\)。
- \(k\geq 3\)
注意到，若 \(x\) 质因数分解后满足 \(p_1p_2p_3...p_m\) 的形式，则将答案在 \(x\) 时记下不会记重。
枚举底数 \(a\)，时间复杂度显然在 \(O(n^{\frac{1}{3}})\) 阶内。然后暴力枚举指数 \(b\)，并打标记防止记重（标记数组用 map 存）。统计记录下个数。
这样时间复杂度 \(O(n^{\frac{1}{3}}\log n)\)，可以接受。45pts。
- \(k=2\)
相当于在 \(k\ge 3\) 的基础上多加了一堆完全平方数。
已知所有 \(\le n\) 的完全平方数的数量为 \(\left\lfloor \sqrt n \right\rfloor\)。但是直接加上会记重，原因是那些 \(k \ge 3\) 中的方案里也有完全平方数，比如 \(4^3=8^2=64\)。于是你只要记下那些 \(k \ge 3\) 中的方案的完全平方数的个数，容斥掉就可以了。
总时间复杂度还是 \(O(n^{\frac{1}{3}}\log n)\)。100pts。
点击查看代码
#include<bits/stdc++.h>
#define int long long
#define rint register int
#define For(i,l,r) for(rint i=l;i<=r;++i)
#define FOR(i,r,l) for(rint i=r;i>=l;--i)
using namespace std;
int n, k, ans, und;
map<int, bool> vis;
int qpow(int a, int b) {
int res = 1;
for (; b; b >>= 1, a = a * a) {
if(b & 1) res = res * a;
}
return res;
}
signed main() {
cin >> n >> k;
if(k == 1) cout << n << '\n';
else if(k >= 2){
for (int i = 2; i * i * i <= n; ++i) {
for (int j = i * i, kk = 2; ; ) {
if(j > n/i) break;
j *= i, kk++;
if(kk < k) continue;
if(vis[j]) continue;
vis[j] = 1;
ans++;
if((int)sqrtl(j)*sqrtl(j) == j) und++;
}
}
if(k >= 3) cout << ans+1 << '\n';
else cout << (int)sqrtl(n) + ans - und << '\n';
}
return 0;
}