淄博 建网站,html5网站网址,学校网站建设,app图标制作2022年中国高校计算机大赛-团队程序设计天梯赛#xff08;GPLT#xff09;上海理工大学校内选拔赛
2024.8.2 12:00————16:00
过题数790/1500 补题数943.33/1500 AB Problem Komorebi的数学课 次佛锅 Setsuna的K数列 Wiki下象棋 黄金律法 天气预报 叠硬币 AB Problem ag…2022年中国高校计算机大赛-团队程序设计天梯赛GPLT上海理工大学校内选拔赛
2024.8.2 12:00————16:00
过题数790/1500 补题数943.33/1500 AB Problem Komorebi的数学课 次佛锅 Setsuna的K数列 Wiki下象棋 黄金律法 天气预报 叠硬币 AB Problem again 史东薇尔城 取模 剪绳子 数硬币 截肢葛瑞克 上海施工小学 A - AB Problem
题解 给出一个长度为n的数组对于数组中的每一个数字a再数组中的其他数字中找到一个b使得ab最大。输出n个数字。 找出数组最大值并判断有几个有多个的话输出所有的数字加上最大值的结果即可只有一个的话最大的数字要加上第二大的数字别的加上最大的数字即可。 代码
#includebits/stdc.husing namespace std;
#define int long long
int a[100005];
int an[100005];signed main() {int n;cin n;int ma 0;int ma2 0;for (int i 1; i n; i) {cin a[i];if(a[i] ma)ma a[i];}int t 0;int wz;for (int i 1; i n; i) {if(ma a[i]){wz i;t;continue;}an[i] a[i]ma;if(an[i] ma2)ma2 an[i];}if(t 1) {for (int i 1; i n; i) {if(i wz)an[i] ma2;cout an[i] ;}}else {for (int i 1; i n; i) {if(a[i] ma)an[i] a[i]ma;cout an[i] ;}}return 0;
}B - Komorebi的数学课
题解 输出n的n次方modn2 代码
#includebits/stdc.husing namespace std;
#define int long long
int n;int qpow(int base,int power,int mod) {int res 1;while(power) {if(power 1)res res*base%mod;base base*base%mod;power 1;}return res;
}signed main() {cin n;cout qpow(n,n,n2);return 0;
}C - 次佛锅
题解 第一行给出一串字符串表示这个食材有多少个相同食材可能多次出现。 用map存取查找即可。 代码
#includebits/stdc.husing namespace std;
#define int long long
int n;
string s;
int t;
mapstring,intmp;signed main() {getline(cin,s);string p ;int lt 0;for (int i 0; i s.length(); i) {while((a s[i] s[i] z) || A s[i] s[i] Z) {p ps[i];i;}while(0 s[i] s[i] 9) {lt lt*10 s[i]-0;i;}if(s[i] ) {if(0 s[i-1] s[i-1] 9) {mp[p] lt;p ;lt 0;}}}mp[p] lt;cin t;while(t--) {string q;cin q;q q;cout mp[q] endl;}return 0;
}D - Setsuna的K数列
最近好像总是遇到类似题不知道是不是我的错觉就是这种用位运算代替直接运算的会方便很多但敏感度不够更多的是看感觉。 题解 给定俩个整数n和k创建一个集合A包含k的所有整数次幂去A中任意个元素相加并放进一个新的集合B将B中的元素从小到大排序输出第n项。 可以考虑到其实就是从第1个数字到第n个数字每个位上的1分别代表加上了k的i次方且就是一个递增的序列所以直接快速幂输出即可。 代码
#includebits/stdc.husing namespace std;
#define int long long
int n;
string s;
int t;
mapstring,intmp;signed main() {getline(cin,s);string p ;int lt 0;for (int i 0; i s.length(); i) {while((a s[i] s[i] z) || A s[i] s[i] Z) {p ps[i];i;}while(0 s[i] s[i] 9) {lt lt*10 s[i]-0;i;}if(s[i] ) {if(0 s[i-1] s[i-1] 9) {mp[p] lt;p ;lt 0;}}}mp[p] lt;cin t;while(t--) {string q;cin q;q q;cout mp[q] endl;}return 0;
}E - Wiki下象棋
当时写了dfs怎么都想不起来bfs怎么写最后果然是没有写出来。dfs一直tle优化也没用。 题解 t组数据每组给出棋盘的行列数和每个棋子的个数坐标起点和终点。 bfs跑俩遍就可以对于马脚特判一下。 代码
#includebits/stdc.husing namespace std;
#define int long long
const int N 310;
int dx[] {-2,-2,-1,1,2,2,1,-1};
int dy[] {-1,1,2,2,1,-1,-2,-2};
int t;
bool st[N][N];
int vis[N][N];
int n,m,k,a,b,c,d;
int ans 1e9;
int ans1 1e9;
typedef pairint,int PII;void bfs(int x,int y) {queuePIIq;memset(vis,-1,sizeof vis);vis[x][y] 0;q.push({x,y});while(!q.empty()) {xq.front().first;yq.front().second;for (int i 0; i 8; i) {int ax xdx[i],ay ydy[i];if(ax 1 || ax n || ay 1 || ay m)continue;if(st[ax][ay])continue;if(vis[ax][ay] -1) {vis[ax][ay] vis[x][y]1;q.push({ax,ay});}}q.pop();}cout vis[c][d] ;return ;
}void bfs1(int x,int y) {queuePIIq;memset(vis,-1,sizeof vis);vis[x][y] 0;q.push({x,y});while(!q.empty()) {x q.front().first;y q.front().second;for (int i 0; i 8; i) {int ax xdx[i],ay ydy[i];if(ax 1 || ax n || ay 1 || ay m)continue;if(dx[i] -2 st[x-1][y])continue;if(dx[i] 2 st[x1][y])continue;if(dy[i] 2 st[x][y1])continue;if(dy[i] -2 st[x][y-1])continue;if(st[ax][ay])continue;if(vis[ax][ay] -1) {vis[ax][ay] vis[x][y]1;q.push({ax,ay});}}q.pop();}cout vis[c][d] endl;return ;
}signed main() {cin t;while(t--) {memset(st,0,sizeof st);cin n m k a b c d;while(k--) {int la,lb;cin la lb;st[la][lb] true;}ans 5000;memset(vis,0,sizeof vis);bfs(a,b);ans1 5000;memset(vis,0,sizeof vis);bfs1(a,b);}
}F - 黄金律法
很奇怪的一道题当时看过的人多直接试了一下结果竟然过了。好像是不等式的知识 题解 有n个武器的属性值和n个魔法的属性值现在要求单个属性对应单个魔法相乘求和的最小值。 一个递增一个递减相乘求和即可。 代码
#includebits/stdc.husing namespace std;
#define int long long
const int N 1e610;
int t;
int w[N],m[N];signed main() {cin t;while(t--) {int n;cin n;for (int i 1; i n; i)cin w[i];sort(w1,w1n);for (int i 1; i n; i)cin m[i];sort(m1,m1n,greaterint());int ans 0;for (int i 1; i n; i) {ans (w[i]*m[i]);}cout ans endl;}return 0;
}G - 天气预报
题解 未来n天的天气用一个字符串来表示0表示晴朗1表示会下青蛙。现在要求找出区间可以一天都不选使得他在这段时间内至少可以出去玩a天休息b天。 对于这段区间的左节点循环遍历右节点二分判断找到最接近的满足条件的日子后面的所有日子都满足直接相加就可以很简单的二分。 代码
#includebits/stdc.husing namespace std;
#define int long long
#define ll long long
const int N 1e610;
int n,a,b;
int aa[N],bb[N];
//晴朗 休息int check(int i,int j) {ll p aa[j] - aa[i-1];ll q bb[j] - bb[i-1];if(p a q b)return 1;return 0;
}signed main() {cin n a b;string s;cin s;s s;for (int i 1; i n; i) {if(s[i] 0) {aa[i] aa[i-1]1;bb[i] bb[i-1];}else {bb[i] bb[i-1]1;aa[i] aa[i-1];}}int ans 0;
// int m 0;
// for (int i 1; i n; i) {
// if(aa[i]-aa[m] a bb[i]-bb[m] b){
// ans (n-i1);
// m;
// }
// }
// for (int i m; i n; i) {
// if(aa[n]-aa[i] a bb[n]-bb[i] b) {
// ans;
// }
// else break;
// }if(a0b0)ans;//特殊情况当a和b均为0时可以一天也不选for(int i1;in;i){ll li,rn;while(lr){ll mid(lr)/2;if(check(i,mid))rmid;else lmid1;}if(check(i,l))ans(n-l1);}cout ans endl;return 0;
}J - 史东薇尔城
题解 有n个节点和m条边询问t次每次siti。需要从si跑回1再跑到ti球最短路径。 也就是从1跑到si再跑到ti。跑一遍Dijkstra然后输出最短距离即可。 代码
#includebits/stdc.h
using namespace std;
#define int long long
const int N 1e610;
int n,m;
int dis[N],vis[N];
const int INF 0x3f3f3f3f;
typedef pairint,intPII;
#define endl \nstruct ty {int to,next,w;
}edge[N1000];int cnt 0;
int head[N];
void add_edge(int u,int v,int w) {cnt;edge[cnt].to v;edge[cnt].w w;edge[cnt].next head[u];head[u] cnt;
}void dij(int x) {priority_queuePII,vectorPII,greaterPIIpq;pq.push({0,x});dis[x] 0;while(!pq.empty()) {int x pq.top().second;pq.pop();//一开始一直写在continue以后跑死循环了if(vis[x])continue;vis[x] 1;for (int i head[x]; i!-1; i edge[i].next) {if(!vis[edge[i].to]) {if(dis[edge[i].to] dis[x] edge[i].w) {dis[edge[i].to] dis[x] edge[i].w;pq.push({dis[edge[i].to],edge[i].to});}}}}
}signed main( ){scanf(%lld %lld,n,m);memset(head,-1,sizeof head);int a,b,c;for (int i 1; i m; i) {scanf(%lld %lld %lld,a,b,c);add_edge(a,b,c);add_edge(b,a,c);}int t;scanf(%lld,t);memset(dis,INF,sizeof dis);memset(vis,0,sizeof vis);dij(1);//别再里面跑浪费时间int si,ti;while(t--) {cin si ti;printf(%lld\n,dis[si]dis[ti]);}return 0;
}L - 剪绳子
题解 十米的绳子C表示在这个位置减一刀A表示在这个位置询问这条绳子的长度。 怀疑是数据太水了暴力跑了一遍就过了。 官方给出的题解是一开始把所有点当成一个绳子然后把每一截绳子练成一个并查集倒着往前遍历C表示连上这俩个并查集A表示查询。储存输出。 代码
#includebits/stdc.husing namespace std;
#define int long long
setdoublep;signed main() {int q;cin q;while(q--) {char s;cin s;double m;cin m;if( s A) {double gg 0;double now 10;for (auto x: p) {if(x m){now x;break;}else gg x;}double res now-gg;printf(%0.5lf\n,res);}else {p.insert(m);}}return 0;
}
