- 福建师范大学第26届低年级程序设计竞赛（重现赛）
试题题解（部分）
-
Yuns LV 4 @ 2023-3-19 18:05:34
A. ACM赛制
直接模拟即可，需要注意总罚时可能会超出int范围，需要用long long保存。
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int MAXN = 1.5e6 + 5;
int n, k, tot = 0, cost = 0, st[MAXN];
void solve() {
scanf("%lld%lld", &n, &k);
tot = cost = 0;
for(int i = 1; i <= n; i++) st[i] = 0;
for(int i = 1; i <= k; i++) {
int id, hh, mm; char msg[15];
scanf("%lld:%lld-%lld:%s", &id, &hh, &mm, msg);
if(st[id] == 1) continue;
if(msg[0] == 'a') { // accepted
++tot;
cost += -20 * st[id] + hh * 60 + mm;
st[id] = 1;
} else { // unaccepted
--st[id];
}
}
printf("%lld %lld", tot, cost);
}
signed main() {
solve();
return 0;
}
H. WF？刚打低程就想着WF？
定位是签到题。给出6个等级的比赛其中分Au、Ag、Cu，可以整体看成18个奖项，按照题意模拟即可。
#include <bits/stdc++.h>
using namespace std;
const int N=100;
int n,a[N];
map<string,int>mp;
string S[N];
int main(int argc, char *argv[]) {
mp["LowerLevelProgrammingCompetition Cu"]=1,S[1]="LowerLevelProgrammingCompetition Cu";
mp["LowerLevelProgrammingCompetition Ag"]=2,S[2]="LowerLevelProgrammingCompetition Ag";
mp["LowerLevelProgrammingCompetition Au"]=3,S[3]="LowerLevelProgrammingCompetition Au";
mp["SchoolCompetition Cu"]=4,S[4]="SchoolCompetition Cu";
mp["SchoolCompetition Ag"]=5,S[5]="SchoolCompetition Ag";
mp["SchoolCompetition Au"]=6,S[6]="SchoolCompetition Au";
mp["ProvincialCompetition Cu"]=7,S[7]="ProvincialCompetition Cu";
mp["ProvincialCompetition Ag"]=8,S[8]="ProvincialCompetition Ag";
mp["ProvincialCompetition Au"]=9,S[9]="ProvincialCompetition Au";
mp["Regional Cu"]=10,S[10]="Regional Cu";
mp["Regional Ag"]=11,S[11]="Regional Ag";
mp["Regional Au"]=12,S[12]="Regional Au";
mp["ECfinal Cu"]=13,S[13]="ECfinal Cu";
mp["ECfinal Ag"]=14,S[14]="ECfinal Ag";
mp["ECfinal Au"]=15,S[15]="ECfinal Au";
mp["WF Cu"]=16,S[16]="WF Cu";
mp["WF Ag"]=17,S[17]="WF Ag";
mp["WF Au"]=18,S[18]="WF Au";
cin>>n;
getchar();
int ans=0;
for(int i=1;i<=n;i++){
string s;
getline(cin,s);
if(ans) continue;
if(s.substr(s.length()-2)!="Fe") {
int x=mp[s];
a[x]++;
while(a[x]>=3){
a[x+1]++;
a[x]-=3;
x++;
}
if(x==18) ans=i;
}
}
if(ans) cout<<ans<<endl;//有WF Au
else {
for(int i=18;i>=1;i--){
if(a[i]){
ans=i;
break;
}
}
if(ans) cout<<S[ans]<<endl;//有奖
else cout<<"-1"<<endl;//Fe
}
}
B. 邪恶？任何邪恶终将绳之以法！
考虑到数据范围，我们应该想办法限制每一次操作最多涉及到 个节点。
由于含有 个节点的满二叉树，深度为 级别。我们操作点 时，可以直接沿着 的父亲方向往上走，直至根节点。
我们定义两个数组 , ，其中这两个数组的含义如下：
代表以 为根节点的子树里有多少个小贼（包括节点 ）；
代表以 为根节点的子树中，所有小贼到节点 的距离之和。
对于修改操作，我们可以在 的范围内修改这两个数组；
对于查询操作，我们在往上走的过程中，维护这期间所经历的节点，并根据这两个数组计算结果。
具体来讲，我们设这一过程经历了节点 ，其中 是 的父亲。 代表以 为根节点的子树， 代表在 中删除 。
那么，我们可以计算出 的小贼数量 ，和 中 个小贼到节点 的距离 。
考虑引入新的变量 ，代表了节点 到节点 的距离（其中节点 对应昊京现在的位置）。则 代表了节点 对节点 的贡献。
对于节点 ，我们计算其所有祖先的贡献，再加上 ，即是查询结果。
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int MAXN = 131071 + 5;
int dist[MAXN], cnt[MAXN], n, q;
int query(int x) {
int res = dist[x], u = x >> 1, last = x, cdist = 1;
while(u) {
int ucnt = cnt[u] - cnt[last];
int udist = dist[u] - dist[last] - cnt[last];
res += udist + ucnt * cdist;
++cdist;
last = u;
u >>= 1;
}
return res;
}
void modify(int x, int st) {
int u = x, cdist = 0;
while(u) {
cnt[u] += st;
dist[u] += st * cdist;
++cdist;
u >>= 1;
}
}
void solve() {
cin >> n >> q;
for(int i = 1; i <= n; i++) cnt[i] = dist[i] = 0;
while(q--) {
int op, x; cin >> op >> x;
if(op == 1) cout << query(x) << "\n";
if(op == 2) modify(x, 1);
if(op == 3) modify(x, -1);
}
}
signed main() {
ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
solve();
return 0;
}
E. 微积分？低程竟然有微积分？
处理前面若干项时，读到‘x‘或’^‘时便可得出一项系数，跟在后面的为指数。
建议最后一项单独处理，判断是否为常数项。
需要注意系数绝对值为1或指数为1时省略，存在常数项、首项为负的情况，小细节较多，比较考察选手的细心程度，考虑全面即可通过。
#include <bits/stdc++.h>
using namespace std;
string s;
int shou=1;//标记首项是否已读入
int fu=1;//存当前系数的符号
int xishu=0,zhishu=0;//存当前项的系数和指数
vector<int>xi,zhi;//存全部的指数和系数
inline int gcd(int x,int y){return y==0?x:gcd(y,x%y);}
int main(int argc, char *argv[]) {
cin>>s;
for(int i=0;i<s.length();i++){
if(s[i]=='y'||s[i]=='\''||s[i]=='=') {}
else if(s[i]>='0'&&s[i]<='9'){
xishu=xishu*10+s[i]-'0';
}
else if(s[i]=='x'){
if(xishu==0) xishu=1;
if(fu==-1) xishu=-xishu;
if(i<s.length()-1){
if(s[i+1]=='^'){
int j=i+2;
while(j<s.length()&&s[j]>='0'&&s[j]<='9'){
zhishu=zhishu*10+s[j]-'0';
j++;
}
i=j-1;
}
else zhishu=1;
}
else zhishu=1;
xi.push_back(xishu);
zhi.push_back(zhishu);
xishu=0,zhishu=0;
}
else if(s[i]=='+'||s[i]=='-'){
if(shou){
shou=0;
if(s[i]=='-') fu=-1;
continue;
}
if(s[i]=='+') fu=1;
else fu=-1;
xishu=0,zhishu=0;
}
}
if(xishu>0){//存在常数项
if(fu==-1) xishu=-xishu;
zhishu=0;
xi.push_back(xishu);
zhi.push_back(zhishu);
}
cout<<"y=";//输出
for(int i=0;i<xi.size();i++){
if(xi[i]<0) {
cout<<"-";
xi[i]=-xi[i];
}
else if(i>0) cout<<"+";
int fenzi=xi[i];
int fenmu=zhi[i]+1;
if(fenzi==fenmu){}
else if(fenzi%fenmu==0){
cout<<fenzi/fenmu;
}
else {
int g=gcd(fenmu,fenzi);
cout<<fenzi/g<<"/"<<fenmu/g;
}
cout<<"x";
if(zhi[i]+1==1){}//指数为1时省略
else cout<<"^"<<zhi[i]+1;
}
cout<<"+C"<<endl;//不定积分要+C!!!
return 0;
}
SCI
Problem Statement
给你个串, 你选出个串拼接而成字典序最小的串
Solution
假设表示第个串, 那么那么一定会排在前面, 很容易证明如果满足那么有即满足传递性.
那么我们就能够先进行一次排序, 然后进行DP, 我们有两种DP方式.
- 首先的是我们强制表示前个串选个并且以串结尾的字典序最小的串.
- 或者为了消除后缀的影响, 我们可以倒过来DP, 我们设表示倒数个串, 选出个串的最小后缀. 这种方法是的
旅行
Problem Statement
个点条边的无向图, 每条边用参数表示, 时刻通过边的代价为求的最小花费时间.
Solution
首先根据题意, 由于边权为, 于是我们索性引入答案参数使得, 由于是常数, 出发时间 是单调递增函数, 的一个关于出发时间的一个单调递减函数, 因此到达的边权等价于一个单峰函数其性质类似二次函数, 我们对其进行最小化跑一边Dijkstra即可, 至于有没有卡SPFA, 本人表示我没刻意卡.
B 蘑菇! 提莫来采蘑菇啦!
这题难度大概在CF2000左右,用来筛选dp比较好的选手
可以很简单的想到用一个来表示走到i这里的最短时间. 用一个来表示走到i这里的方案数.
那么怎么计算从一个位置i使用机器人j能走到的地方呢? 可以发现用第k种机器人的本质是 最多有k种不同的数最长区间. 这是一个经典问题(参考最长连续不重复子序列),用双指针就可以处理. 每走到一个地方,就去扩展用第个机器人能走到的地方r[j]. 有种方案,双指针的时间复杂度为 的时间复杂度为.
不妨设 转移式:. 从i这里,使用第个机器人,能走到这个位置. 此时需要花费的时间,与去比较,取最小值. 注意初始化.其余为正无穷,表示到达0这个位置需要最少花的时间.
如果从i这个地方用第个机器人所花费的时间要比要小,那么 要用去更新.() 如果,说明之前就有方案到达过,且与这次从i过来花费的时间相同. 于是从过来就是一种新方案.,就是加上到达已有的方案数. 注意取模.初始化,其余为.表示到达这个位置初始就有种方案.
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N = 1e6 + 10,mod = 998244353,INF = 1e17;
int n,m;
int a[N],c[N],dp1[N],dp2[N];
int r[35],cnt[35],mp[N][35];
void expand(int stpos,int j)
{
if(mp[a[stpos]][j]) {
mp[a[stpos]][j] -- ;
if(mp[a[stpos]][j] == 0) cnt[j] -- ;
}
while(cnt[j] <= j && r[j] < n) {
if(mp[a[r[j] + 1]][j] == 0) {
if(cnt[j] == j) break;
cnt[j] ++ ;
}
mp[a[r[j] + 1]][j] ++ ;
r[j] ++ ;
}
}
signed main() {
int T;
cin >> T;
while(T--) {
cin >> n >> m;
for(int i=1;i<=n;++i) cin >> a[i];
for(int i=0;i<=m;++i) cin >> c[i];
for(int i=0;i<=n;++i) {
r[i] = dp2[i] = cnt[i] = 0;
dp1[i] = INF;
for(int j=0;j<=m;++j) mp[i][j] = 0;
}
dp1[0] = 0;dp2[0] = 1;
for(int i=0;i<n;++i) //从i开始走
for(int j=0;j<=m;++j) { //用第j个蘑菇
if(j == 0) r[j] = i + 1; //动手采集蘑菇,只能到下一个位置i+1.
else expand(i,j);
if(dp1[r[j]] == dp1[i] + c[j]) dp2[r[j]] = (dp2[r[j]] + dp2[i]) % mod;
if(dp1[r[j]] > dp1[i] + c[j]) {
dp1[r[j]] = dp1[i] + c[j];
dp2[r[j]] = dp2[i];
}
}
cout << dp1[n] << " " << dp2[n] << endl;
}
return 0;
}
D # 锁屏图案? 当然是第k长的最好看!
这题难度定位是稍微做过一些题的选手都要能做出来. 但是榜比较歪,很多人都不看这题.
直接暴力枚举所有的方案数,一共有种方案,不多. 然后判断每种方案是否合法,合法的话计算下距离.
之后时排序,先按距离排,然后按字典序排,比较简单不多说了. 距离的话判相等只要精度误差在以内就认为两种方案是相等的. 因为只有根号2,根号5,而且数量还不会很多.
时间复杂度 //8 * 9是判断合法要的时间,另外1 * 9计算距离
#include<bits/stdc++.h>
#define int long long
using namespace std;
typedef pair<int,int> PII;
const int N = 1e6 + 10;
double eps = 1e-7; //精度取10^-7
struct node {
int res[10];
double dist;
bool operator < (const node & cc) const{
if( abs(dist - cc.dist) > eps) return dist > cc.dist;
//先按距离排
for(int i=1;i<=9;++i) { //再按字典序排
if(res[i] != cc.res[i]) return res[i] > cc.res[i];
}
}
};
vector<node> v;
int a[10] = {0,1,2,3,4,5,6,7,8,9};
PII pos[10];
bool check(int l,int r,int mid) //判断l和r是否是连着,且mid在它们后面,这是非法的
{
int midpos,lpos,rpos;
for(int i=1;i<=9;++i) {
if(a[i] == mid) midpos = i;
if(a[i] == l) lpos = i;
if(a[i] == r) rpos = i;
}
if(lpos > rpos) swap(lpos,rpos);
if(lpos + 1 == rpos && midpos > rpos) {
return false;
}
return true;
}
double cal(int x,int y) //计算距离
{
double res = (pos[x].first - pos[y].first) * (pos[x].first - pos[y].first);
res += (pos[x].second - pos[y].second) * (pos[x].second - pos[y].second);
return sqrt(res);
}
void init()
{
int n = 3;
for(int i=1;i<=3;++i)
{
for(int j=1;j<=3;++j) {
pos[3*(i-1) + j].first = i; //初始化每行的x坐标
pos[i + 3*(j-1)].second = i; //初始化每行的y坐标
}
}
do { //这里用的是do{}while(next_permutation()),写dfs也可以
bool ok = true;
ok &= check(1,3,2);ok &= check(1,7,4); //1-3 连着且2再他们后面,其它相同
ok &= check(3,9,6);ok &= check(7,9,8);
ok &= check(3,7,5);ok &= check(1,9,5);
ok &= check(2,8,5);ok &= check(4,6,5);
if(ok == false) continue;
node tmp;tmp.dist = 0;
for(int i=1;i<=9;++i) {
tmp.res[i] = a[i];
if(i!=1) tmp.dist += cal(tmp.res[i],tmp.res[i-1]);
}
v.push_back(tmp);
}while(next_permutation(a+1,a+1+9));
sort(v.begin(),v.end());
}
signed main() {
init();
int T;cin >> T;
while(T--) {
int k;cin >> k;
for(int i=1;i<=9;++i) cout << v[k-1].res[i] << " ";cout << endl;
}
return 0;
}
#include<bits/stdc++.h> //没精度误差
#define int long long
using namespace std;
typedef pair<int,int> PII;
const int N = 1e6 + 10;
struct node {
int id[10],dist[3];
};
int cmp2(int x1,int x2,int x3)
{
if(x1 == 0 && x2 == 0 && x3 == 0) return 0;
if(x1 >= 0 && x2 >= 0 && x3 >= 0) return 1;
if(x1 <= 0 && x2 <= 0 && x3 <= 0) return -1;
int flag = 0,res1 = 0,res2 = 0;
int plan1 = 0,plan2 = 0;
vector<PII> v;
v.push_back({x1,5*x1*x1});
v.push_back({x2,2*x2*x2});
v.push_back({x3,1*x3*x3});
sort(v.begin(),v.end());
if(v[0].first <= 0 && v[1].first <= 0 && v[2].first >= 0) {
res1 = v[2].second - v[0].second - v[1].second;
res2 = 4 * v[0].second * v[1].second;
if(res1 < 0) return -1;
res1 = res1 * res1;
if(res1 > res2) return 1;
plan1 = -1;
}
return -cmp2(-x1,-x2,-x3);
assert(0);
}
int cmp(node n1,node n2)
{
int t[5];
for(int i=0;i<3;++i) t[i] = n1.dist[i] - n2.dist[i];
int res = cmp2(t[0],t[1],t[2]);
if(res == 0) {
for(int i=1;i<=9;++i) {
if(n1.id[i] != n2.id[i]) return n1.id[i] > n2.id[i];
}
}
if(res == 1) return 1;
return 0;
}
vector<node> v;
int a[10] = {0,1,2,3,4,5,6,7,8,9};
PII pos[10];
int check(int l,int r,int mid)
{
int midpos,lpos,rpos;
for(int i=1;i<=9;++i) {
if(a[i] == mid) midpos = i;
if(a[i] == l) lpos = i;
if(a[i] == r) rpos = i;
}
if(lpos > rpos) swap(lpos,rpos);
if(lpos + 1 == rpos && midpos > rpos) return false;
return true;
}
PII cal(int x,int y)
{
int delx = abs(pos[x].first - pos[y].first);
int dely = abs(pos[x].second - pos[y].second);
if(delx == 0 || dely == 0) return {2,delx + dely};
if(max(delx,dely) / min(delx,dely) == 1) return {1,delx};
return {0,1};
}
void init()
{
int n = 3;
for(int i=1;i<=3;++i)
{
for(int j=1;j<=3;++j) {
pos[3*(i-1) + j].first = i;
pos[i + 3*(j-1)].second = i;
}
}
do {
bool ok = true;
ok &= check(1,3,2);ok &= check(1,7,4);
ok &= check(3,9,6);ok &= check(7,9,8);
ok &= check(3,7,5);ok &= check(1,9,5);
ok &= check(2,8,5);ok &= check(4,6,5);
if(ok == false) continue;
node tmp;
for(int i=0;i<3;++i) tmp.dist[i] = 0;
for(int i=1;i<=9;++i) {
tmp.id[i] = a[i];
if(i!=1) {
PII res = cal(tmp.id[i],tmp.id[i-1]);
tmp.dist[res.first] += res.second;
}
}
v.push_back(tmp);
}while(next_permutation(a+1,a+1+9));
sort(v.begin(),v.end(),cmp);
}
signed main() {
init();
int T;cin >> T;
while(T--) {
int k;cin >> k;
for(int i=1;i<=9;++i) cout << v[k-1].id[i] << " ";cout << endl;
}
return 0;
}
0 条评论
目前还没有评论...