T1 涂色游戏
这道题目还是比较简单的
容易发现，位于
(
x
i
,
y
i
)
(x_i,y_i)
(xi,yi) 的格子的颜色只取决于
x
i
x_i
xi 行与
y
i
y_i
yi 列的颜色。
这时候可以想到开两个数组，分别存储列与行的绘画信息，然后发现前后的互相覆盖可以通过存储绘画顺序来得出。
考虑
L
i
L_i
Li 表示第
i
i
i 行最后一次被染成什么颜色，
U
i
U_i
Ui 表示第
i
i
i 列最后一次被染成什么颜色，同时记录下这些操作的时间先后顺序。
那么对于最终的格子
(
i
,
j
)
(i,j)
(i,j) ，它的颜色就是
L
i
L_i
Li 和
U
j
U_j
Uj 中更晚的一个，简单判断一下然后输出即可。
#include<bits/stdc++.h>
using namespace std;
int read(){
int x=0,f=1;char ch=getchar();
while(ch>'9'||ch<'0') {
if(ch=='-') f=-1;
ch=getchar();
}
while(ch>='0'&&ch<='9') x=x*10+ch-'0',ch=getchar();
return x*f;
}
const int N = 1e5 + 5;
int n, m, q;
pair<int, int> L[N], U[N];
void Init() {
for (int i = 1; i <= n; ++i) {
L[i] = make_pair(0, 0);
}
for (int i = 1; i <= m; ++i) {
U[i] = make_pair(0, 0);
}
}
int main() {
int T=read();
while (T--){
n=read(),m=read(),q=read();
Init();
for (int i = 1; i <= q; i++) {
int opt=read(),x=read(),y=read();
if (opt == 0) {
L[x] = make_pair(y, i);
} else {
U[x] = make_pair(y, i);
}
}
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
if (L[i].second > U[j].second) {
cout << L[i].first << ' ';
} else {
cout << U[j].first << ' ';
}
}
puts("");
}
}
return 0;
}
T2 幂次
这道题如果在考场上不认真分析也就会做不出来
首先就是骗分：
发现
k
=
1
k=1
k=1 ，就直接输出
n
n
n 就行了
考虑一个比较简单的暴力, 枚举 [ 1 , n ] [1, n] [1,n] 中的每个数作为 a a a , 然后枚举 b b b , 直到 a b ≥ n a^{b} \geq n ab≥n 就让 a + + \mathrm{a}++ a++ 然后重新枚举 b b b , 每个没出现过的数使 a n s + + ans ++ ans++。
先不考虑去重, 我们来思考如何优化这个暴力。注意到当我们枚举的 b b b 增加时, 使 a b a^{b} ab 首次 ≥ n \geq n ≥n 的 a a a 会越来越小，由此我们可以对每个 b b b 二分求出一个 a a a 的上界，此时 a a a 的上界是 n n n 次根号级别的。
因为 2 60 ≥ 1 0 18 2^{60} \geq 10^{18} 260≥1018 , 所以 b b b 实际的范围并不大。对于 k ≥ 3 k \geq 3 k≥3 的情况我们都可以枚举 b b b 求出 a a a 的上界然后直接暴力求所有快速幂做了。剩下的情况中, k = 1 k=1 k=1 时答案显然为 n n n , 那么 k = 2 k=2 k=2 时如何做?
此时回来考虑去重, 所以求完快速幂后再枚举每个 ≤ b \leq b ≤b 的 x x x 作为新的指数。然后对当前求得的 a b a^{b} ab 开 x x x 次方根, 看是否有正整数解, 就可以判定是否与之前计算过的重复了。
此时
k
=
2
k=2
k=2 的情况就迎刃而解了，我们直接令初始
a
n
s
为
n
ans 为 \sqrt{n}
ans为n 即可。
还要注意
a
a
a 为
1
1
1 的情况, 在初始答案上略作修改就行。
时间复杂度比较抽象, 我不会表示, 交了反正能过。
#include<bits/stdc++.h>
using namespace std;
#define int long long
int read() {
int x=0,f=1;
char ch=getchar();
while(ch>'9'||ch<'0') {
if(ch=='-') f=-1;
ch=getchar();
}
while(ch>='0'&&ch<='9') x=x*10+ch-'0',ch=getchar();
return x*f;
}
using namespace std;
using i64 = long long;
i64 n, a[100010];
int k;
long double Qpow(int x, int y) {
long double res = 1, base = x;
for (; y; y >>= 1, base *= base) {
if (y & 1) {
res *= base;
}
}
return res;
}
int GetRoot(int x, int y) {
int l = 1, r = x;
while (l <= r) {
int mid = (l + r) >> 1;
if (Qpow(mid, y) > x) r = mid - 1;
else l = mid + 1;
}
return r;
}
signed main() {
n=read(),k=read();
i64 res = 1;
int lim = 0;
for (int i = k; ; ++i) {
int v = GetRoot(n, i);
lim = i;
if (v <= 1) break;
a[i] = v - 1;
}
for (int i = lim - 1; i >= k; --i) {
for (int j = i + i; j <= lim; j += i) {
a[i] -= a[j];
}
}
for (int i = k; i < lim; ++i) {
res += a[i];
}
cout << res << '\n';
return 0;
}
T3
很显然的一个结论就是连接的路径一定不能相交。证明考虑相交的时候交换两个顶点的顺序一定更优。
假设已经连接的点的集合为
S
S
S ，那么
S
S
S 一定在凸多边形上是连续的，因此有一个很显然的
D
P
DP
DP: 设
f
(
i
,
j
,
0
/
1
)
f(i, j, 0 / 1)
f(i,j,0/1) 表示从
k
k
k 逆时针转选了
i
i
i 个，顺时针转选了
j
j
j 个，当前在左侧
/
/
/ 右侧。转移很明显（用
L
(
x
)
L(x)
L(x) 表示
k
k
k 逆时针开始的第
x
x
x 个，
R
(
x
)
R(x)
R(x) 表示顺时针的第
x
x
x 个）：
f ( i , j , 0 ) ← f ( i − 1 , j , 0 ) + dis ( L ( i − 1 ) , L ( i ) ) f ( i , j , 0 ) ← f ( i − 1 , j , 1 ) + dis ( R ( j ) , L ( i ) ) f ( i , j , 1 ) ← f ( i , j − 1 , 0 ) + dis ( L ( i ) , R ( j ) ) f ( i , j , 1 ) ← f ( i , j − 1 , 1 ) + dis ( R ( j − 1 ) , R ( j ) ) \begin{array}{l} f(i, j, 0) \leftarrow f(i-1, j, 0)+\operatorname{dis}(L(i-1), L(i)) \\ f(i, j, 0) \leftarrow f(i-1, j, 1)+\operatorname{dis}(R(j), L(i)) \\ f(i, j, 1) \leftarrow f(i, j-1,0)+\operatorname{dis}(L(i), R(j)) \\ f(i, j, 1) \leftarrow f(i, j-1,1)+\operatorname{dis}(R(j-1), R(j)) \end{array} f(i,j,0)←f(i−1,j,0)+dis(L(i−1),L(i))f(i,j,0)←f(i−1,j,1)+dis(R(j),L(i))f(i,j,1)←f(i,j−1,0)+dis(L(i),R(j))f(i,j,1)←f(i,j−1,1)+dis(R(j−1),R(j))
最终答案就是
min
0
≤
i
<
n
min
(
f
(
i
,
n
−
i
−
1
,
0
)
,
f
(
i
,
n
−
i
−
1
,
1
)
)
\min _{0 \leq i<n} \min (f(i, n-i-1,0), f(i, n-i-1,1))
min0≤i<nmin(f(i,n−i−1,0),f(i,n−i−1,1)) 。
题目要求输出方案，那么就在转移的过程中再记录一个
from
(
i
,
j
,
0
/
1
)
\operatorname{from}(i, j, 0 / 1)
from(i,j,0/1) 表示当前状态是又哪一个转移过来的，最后遍历输出即可。
贴一个证明过程
#include<bits/stdc++.h>
#define int long long
int read(){
int x=0,f=1;char ch=getchar();
while(ch>'9'||ch<'0') {
if(ch=='-') f=-1;
ch=getchar();
}
while(ch>='0'&&ch<='9') x=x*10+ch-'0',ch=getchar();
return x*f;
}
using namespace std;
const int N=1e3+10;
struct node {
double x,y;
} a[N];
struct point {
int l,r,x;
} fa[N][N][2];
int n,m,T;
double f[N][N][2],ans;
bool chmin(double& x,double y) {
if(x>y) x=y;
return (x==y);
}
int ex(int x) {
if(x<=0) x+=n;
if(x>n) x-=n;
return x;
}
double dist(int x,int y) {
return sqrt((a[x].x-a[y].x)*(a[x].x-a[y].x)+(a[x].y-a[y].y)*(a[x].y-a[y].y));
}
signed main() {
n=read();
for(int i=1; i<=n; ++i) cin>>a[i].x>>a[i].y;
double maxn=-1e9;
for(register int i=1; i<=n; ++i) {
if(a[i].y>maxn) {
maxn=a[i].y;
m=i;
}
}
for(register int i=0; i<=n; ++i) for(register int j=0; j<=n; ++j) f[i][j][0]=f[i][j][1]=1e18;
f[0][0][0]=f[0][0][1]=0;
for(register int len=1; len<n; ++len) {
for(register int l=0; l<=len; ++l) {
int r=len-l;
if(l&&chmin(f[l][r][0],f[l-1][r][0]+dist(ex(m+l),ex(m+l-1)))) fa[l][r][0]=(point) {
l-1,r,0
};
if(l&&chmin(f[l][r][0],f[l-1][r][1]+dist(ex(m+l),ex(m-r)))) fa[l][r][0]=(point) {
l-1,r,1
};
if(r&&chmin(f[l][r][1],f[l][r-1][0]+dist(ex(m-r),ex(m+l)))) fa[l][r][1]=(point) {
l,r-1,0
};
if(r&&chmin(f[l][r][1],f[l][r-1][1]+dist(ex(m-r),ex(m-r+1)))) fa[l][r][1]=(point) {
l,r-1,1
};
}
}
ans=1e18;
point jump;
for(register int i=0; i<n; ++i) {
if(f[i][n-i-1][0]<ans) {
ans=f[i][n-i-1][0];
jump=(point) {
i,n-i-1,0
};
}
if(f[i][n-i-1][1]<ans) {
ans=f[i][n-i-1][1];
jump=(point) {
i,n-i-1,1
};
}
}
printf("%lld ",m);
stack<int> s;
while(jump.l>0||jump.r>0) {
s.push((jump.x==0?ex(m+jump.l):ex(m-jump.r)));
jump=fa[jump.l][jump.r][jump.x];
}
while(!s.empty()) printf("%lld ",s.top()),s.pop();
return 0;
}
T4
这道题骗分要随机化，但是随机化我不会，老师只说了random,所以就先学随机种子
考场随机需谨慎，提防爆零两行泪。
附一个链接 https://blog.csdn.net/yeepom/article/details/8625184
还有一个 ：https://blog.csdn.net/xiyangxiaoguo/article/details/104847770
说实在的，考试时打死我我也想不上来用随机数乱搞，就算想到了，也照样不知道怎么用，分析实际情况，我选择写特殊性性质
对于
k
=
1
k=1
k=1 的情况 就是求极差
对于
k
=
2
k=2
k=2 的情况
考虑将小的数放上面，大的数放下面。
思考一下这样为什么是对的？考虑全局最小值和全局最大值所在的行，显然放在两行不劣于放在同一行，设最小值放上面，最大值放下面，那么要想让上面的数尽量小，下面的数尽量大，就是上面的方法。
下面给出部分分的代码
if(k==1){
int minn=1e9,maxn=-1e9;
for(int i=1;i<=n;i++){
minn=min(minn,a[1][i]);
maxn=max(maxn,a[1][i]);
}
printf("%d\n",maxn-minn);
}
k = 1 , 10 p t s k=1,10pts k=1,10pts
FOR(i,0,k-1) FOR(j,1,n){
b[i][j]=rd;
if(b[i][j]>mxx) mxx=b[i][j],mxl=j,mxa=i;
if(b[i][j]<mnn) mnn=b[i][j],mnl=j,mna=i;
}
ans=max(mxx-b[mna^1][mnl],b[mxa^1][mxl]-mnn);
FOR(j,1,n){
if(j==mxl||j==mnl) continue;
int tmp1=max(mxx-b[0][j],b[1][j]-mnn);
int tmp2=max(mxx-b[1][j],b[0][j]-mnn);
ans=max(ans,min(tmp1,tmp2));
}
printf("%d\n",ans);
k
=
2
,
20
p
t
s
k=2,20pts
k=2,20pts
其实再加上暴力搜索就又能拿
10
p
t
s
10pts
10pts
CCF如果数据水，就又能操过去几个点
int res;
void dfs(int x){
if(x>n){
int tmp=0;
FOR(i,0,k-1){
int mx=0,mn=INF;
FOR(j,1,n) mx=max(mx,p[i][j]),mn=min(mn,p[i][j]);
tmp=max(tmp,mx-mn);
}
res=min(res,tmp);
return;
}
FOR(j,0,k-1){
FOR(i,0,k-1) p[(j+i)%k][x]=a[i][x];
dfs(x+1);
}
}
void solve3(){
while(T--){
n=rd;res=INF;
FOR(i,0,k-1) FOR(j,1,n) a[i][j]=rd;
dfs(1);printf("%d\n",res);
}
}
本题拿捏分数： 40 p t s 40pts 40pts
