当前位置: 首页 > news >正文

春季测试 2023 我的题解

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 abn 就让 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} 2601018 , 所以 b b b 实际的范围并不大。对于 k ≥ 3 k \geq 3 k3 的情况我们都可以枚举 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} ansn 即可。
还要注意 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(i1,j,0)+dis(L(i1),L(i))f(i,j,0)f(i1,j,1)+dis(R(j),L(i))f(i,j,1)f(i,j1,0)+dis(L(i),R(j))f(i,j,1)f(i,j1,1)+dis(R(j1),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)) min0i<nmin(f(i,ni1,0),f(i,ni1,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


http://www.mrgr.cn/news/62201.html

相关文章:

  • golang的多表联合orm
  • 程序员修仙传
  • synchronized的优化
  • 使用TimeShift备份和恢复Ubuntu Linux
  • 小米充电宝哪款好用?2024年西圣、小米、罗马仕充电宝全方位测评
  • [QUIC] Packets 和 Frames 概述
  • 达梦数据库在终端/控制台交互查询SQL语句,查询结果导出excel
  • Openjudge:向量点积计算
  • 【Vulnhub靶场】DC-7
  • YOLOv9模型重新参数化,将yolo.pt转为yolo-converted.pt
  • 长文 | 我如何使用 git
  • 【JavaEE】【多线程】进阶知识
  • Comsol CPU水冷散热系统流热固多场耦合仿真
  • el-datepicker此刻按钮点击失效
  • ts:常见的内置数学方法(Math)
  • 面向对象编程——重写和多态
  • UART-通用异步收发器
  • 推荐使用 CompletableFuture 框架进行异步操作,很强很方便
  • 从一到无穷大 #38:讨论 “Bazel 集成仅使用 Cmake 的依赖项目” 通用方法
  • 智航船舶租赁综合管理系统
  • 【C++刷题】力扣-#575-分糖果
  • python的lambda实用技巧
  • 深度学习之激活函数
  • 避免关键任务延迟的资源分配方法
  • Golang高级语法-工具链
  • 拓展学习-golang的基础语法和常用开发工具