第五届辽宁省大学生程序设计竞赛（大连）题解

第五届辽宁省大学生程序设计竞赛（大连）

Prepared by Beater , Core_65536

A.爱上字典

思路：

不断读入字符串，将大写字母全转换成小写字母，特殊字符忽略，将每个字符串存入map中，读到数字就退出。

读入已经会的n个单词，如果这个单词在map中则将这个单词从map中删去，答案就是map中剩余的字符串个数

代码：

#include

using namespace std;

typedef long long ll;

#define endl '\n'

void solve()

{

mapmp;

string s;

while(1)

{

cin>>s;

//mp[s]++;

int f=0;

for(auto i:s)

if(isdigit(i))

{

f=1;

break;

}

if(f) break;

string t;

for(auto i:s)

if(isupper(i)) t+=tolower(i);

else if(islower(i)) t+=i;

mp[t]++;

}

int t=0;

for(auto i:s) t=t*10+(i-'0');

while(t--)

{

string s;

cin>>s;

if(mp.count(s)) mp.erase(s);

}

cout<

}

int main (){

ios::sync_with_stdio(0);

cin.tie(0);

cout.tie(0);

int t=1;

// cin>>t;

while(t--){

solve();

}

return 0;

}

B.比分幻术

思路：

读入字符串，交换一下两个比分，输出

题目还没看，队友样例都没测就交了（

代码：

#include

using namespace std;

typedef long long ll;

#define endl '\n'

void solve(){

string s; cin>>s;

swap(s[0],s[2]);

cout<

}

int main (){

ios::sync_with_stdio(0);

cin.tie(0);

cout.tie(0);

int t=1;

// cin>>t;

while(t--){

solve();

}

return 0;

}

C.插排串联

思路：

dfs求出每个插座需要承载的功率，将所有插座的承载功率排个序，再将每个插排的限制功率排个序，按顺序依次匹配，若无法承载功率则输出"NO"（包括根节点）否则输出"YES"

代码：

#include

using namespace std;

typedef long long ll;

#define endl '\n'

#define int long long

vectorg[100010];

int n,f[100010],a[100010];

int sum[100010];

vectorvt;

void dfs(int u,int fa)

{

if(g[u].size()==1&&u!=0)

{

vt.push_back(u);

sum[u]=a[u];

return ;

}

sum[u]=0;

for(auto v:g[u])

{

if(v==fa) continue;

dfs(v,u);

sum[u]+=sum[v];

}

}

int vis[100010];

void solve()

{

cin>>n;

for(int i=1;i<=n;i++)

{

vis[i]=0;

cin>>f[i]>>a[i];

g[f[i]].push_back(i);

g[i].push_back(f[i]);

}

dfs(0,-1);

for(auto i:vt) vis[i]=1;

vectorrs;

vectorra;

for(int i=1;i<=n;i++) if(!vis[i]) rs.push_back(sum[i]);

for(int i=1;i<=n;i++) if(!vis[i]) ra.push_back(a[i]);

sort(rs.begin(),rs.end());

sort(ra.begin(),ra.end());

for(int i=0;i

if(rs[i]>ra[i])

{

cout<<"NO\n";

return ;

}

int s=0;

for(auto i:g[0])

{

s+=sum[i];

}

if(s>2200)

{

cout<<"NO\n";

return ;

}

cout<<"YES\n";

}

signed main ()

{

ios::sync_with_stdio(0);

cin.tie(0);

cout.tie(0);

int t=1;

// cin>>t;

while(t--){

solve();

}

return 0;

}

D.都市叠高

思路：

诈骗题，看着像计算几何实际就是一个dp

每一次叠楼层增长的高度一定是凸包中某两个点的线段距离，考虑到n为5000，直接暴力\(n^2\)求出所有点两两之间的距离，当选择两个点\((j,i)\)后，这两个点之间的所有点都将失效，因此状态应该从第一个点j前面转移而来，状态转移方程:

$ dp_i =dp_{j-1} + dis(j,i) $

时间复杂度\(O(n^2)\)

代码：

#include

using namespace std;

typedef long long ll;

#define endl '\n'

ll n,x[6010],y[6010];

long double dis(int i,int j)

{

return sqrtl(powl(x[i]-x[j],2.0)+powl(y[i]-y[j],2.0));

}

long double dp[6010];

void solve()

{

scanf("%d",&n);

for(int i=1;i<=n;i++) scanf("%lld %lld",&x[i],&y[i]);

dp[0]=0;

for(int i=1;i<=n;i++)

{

dp[i]=dp[i-1];

for(int j=1;j

{

long double d=dis(i,j);

dp[i]=max(dp[i],dp[j-1]+d);

}

}

long double ans1=0;

for(int i=1;i<=n;i++) ans1=max(ans1,dp[i]);

printf("%.20llf\n",ans1);

}

int main ()

{

int t=1;

// cin>>t;

while(t--){

solve();

}

return 0;

}

E.俄式简餐

思路：

若n和m有一边可以被4整除，则用俄罗斯方块2填满

1

1

1

1

若n和m有一边减去6后能被4整除，另一条边能被2整除

则这样填满

1

1

1

2

2

2

4

4

4

4

1

3

3

3

3

2

5

5

5

5

首先由题得，当\(nm/4\)不整除时必定无解。

然后发现当n或m整除4时可以轻松构造。

所以此时还剩下：nm整除4 且 nm都不为4倍数 的情况。

于是我们知道，这种情况即n、m至少有一个是2的倍数。

于是从最小的开始考虑，便构造出了\(6*2\)的情况，接着发现可以递推得出\((6+4k)*2\)的构造方式。

又考虑到\(n*2\)的构造方式只对\((6+4k)*2\)或\(4*2\)有解。

所以我们知道，以上即为所有情况。

代码：

#include

using namespace std;

typedef long long ll;

#define endl '\n'

void solve(){

int n,m;

cin>>n>>m;

vector > ans(n+1,vector (m+1));

if(m%4==0){

int cnt=1;

for(int i=1;i<=n;i++)

{

int count=0;

for(int j=1;j<=m;j++)

{

ans[i][j]=cnt;

count++;

if(count==4){

count=0;

cnt++;

}

}

}

}else if(n%4==0){

int cnt=1;

for(int j=1;j<=m;j++){

int count=0;

for(int i=1;i<=n;i++){

ans[i][j]=cnt;

count++;

if(count==4){

count=0;

cnt++;

}

}

}

}else if(m>=6&&(m-6)%4==0&&n%2==0){

int cnt=1;

auto sd=[&](int x,int y){

for(int j=y;j

ans[x+1][j]=cnt;

}

ans[x][y]=cnt;

cnt++;

for(int j=y+3;j

ans[x+1][j]=cnt;

}

ans[x][y+5]=cnt;

cnt++;

for(int j=y+1;j

ans[x][j]=cnt;

}

cnt++;

};

for(int i=1;i<=n;i+=2){

sd(i,1);

}

for(int i=1;i<=n;i++){

int count=0;

for(int j=7;j<=m;j++){

ans[i][j]=cnt;

count++;

if(count==4){

count=0;

cnt++;

}

}

}

}else if(n>=6&&(n-6)%4==0&&m%2==0){

int cnt=1;

auto sd1=[&](int x,int y){

for(int i=x;i

ans[i][y]=cnt;

}

ans[x][y+1]=cnt;

cnt++;

for(int i=x+3;i

ans[i][y]=cnt;

}

ans[x+5][y+1]=cnt;

cnt++;

for(int i=x+1;i

ans[i][y+1]=cnt;

}

cnt++;

};

for(int j=1;j<=m;j+=2){

sd1(1,j);

}

for(int j=1;j<=m;j++){

int count=0;

for(int i=7;i<=n;i++){

ans[i][j]=cnt;

count++;

if(count==4){

count=0;

cnt++;

}

}

}

}else{

cout<<"NO"<

return ;

}

cout<<"YES"<

for(int i=1;i<=n;i++){

for(int j=1;j<=m;j++){

cout<

}

cout<

}

}

int main (){

ios::sync_with_stdio(0);

cin.tie(0);

cout.tie(0);

int t=1;

cin>>t;

while(t--){

solve();

}

return 0;

}

G.顾影自怜

思路：

二分加st表。

对于一个元素x，找出右边界使得这个区间内最大值为x，找出元素x出现k次时的下标，这个区间就是贡献。例如：3 3 2 3 1 2 4，当k为3时，对于第一个元素3下标为1，第k个3下标为4，右边界为6，那么这一部分贡献就是6-4+1=3（这个只是单纯的加1），即（3 3 2 3）、（3 3 2 3 1）、（3 3 2 3 1 2）都可以为答案。接下来统计左边的贡献，向左找左边界，使该元素左边的元素都比他小，这样不会造成重复统计，例如3 1 2 3 3 2 3 1 2 4，（3 3 2 3）、（2 3 3 2 3）、（1 2 3 3 2 3）都可以为答案。我们将左右两边的贡献相乘就是这个下标的元素的总贡献，将所有元素的贡献相加即可

时间复杂度\(O(nlog)\)

代码：

#include

using namespace std;

typedef long long ll;

#define endl '\n'

typedef unsigned long long ull;

const int MAXN=2e6+7;

int Log2[MAXN],Min[MAXN][21],Max[MAXN][21];

void solve(){

int n,k;

cin>>n>>k;

int a[n+1];

for(int i=1;i<=n;i++){

cin>>a[i];

}

for(int i=1;i<=n;++i){

Min[i][0]=a[i];

Max[i][0]=a[i];

}

for(int i=2;i<=n;++i){

Log2[i]=Log2[i/2]+1;

}

for(int i=1;i<=20;++i){

for(int j=1;j+(1<

Min[j][i]=min(Min[j][i-1],Min[j+(1<<(i-1))][i-1]);

Max[j][i]=max(Max[j][i-1],Max[j+(1<<(i-1))][i-1]);

}

}

vector > idx(n+1);

vector vis(n+1);

for(int i=1;i<=n;++i){

idx[a[i]].push_back(i);

vis[i]=idx[a[i]].size()-1;

}

auto check=[&](int l,int r){

int s=Log2[r-l+1];

int ma=max(Max[l][s],Max[r-(1<

if(ma<=a[l]){

return 1;

}else{

return 0;

}

};

auto check1=[&](int l,int r){

int s=Log2[r-l+1];

int ma=max(Max[l][s],Max[r-(1<

if(ma

return 1;

}else{

return 0;

}

};

ull ans=0;

for(int i=1;i<=n;i++){

if(vis[i]+k-1>=idx[a[i]].size()){

continue;

}

int left=i,right=n+1;

while(left

int mid=(left+right)/2;

if(check(i,mid)==1){

left=mid+1;

}else{

right=mid;

}

}

int rico=left-1;

int cnt=idx[a[i]][vis[i]+k-1];

int leco=i;

if(i>1){

left=1,right=i;

while(left

int mid=(left+right)/2;

if(check1(mid,i-1)==1){

right=mid;

}else{

left=mid+1;

}

}

if(left>=1&&left

leco=left;

}

}

if(cnt<=rico){

ll st1=(rico-cnt+1);

ll st2=(i-leco+1);

ans+=st1*st2;

}

}

cout<

}

int main (){

ios::sync_with_stdio(0);

cin.tie(0);

cout.tie(0);

int t=1;

cin>>t;

while(t--){

solve();

}

return 0;

}

J.结课风云

思路：

若该学生已经及格则跳过，若该学生要挂科了，则给他加平时分（这里有个上限），如果捞起来了则统计答案

代码：

#include

using namespace std;

typedef long long ll;

#define endl '\n'

void solve(){

int n;

cin>>n;

int a,b,c;

cin>>a>>b>>c;

int x[n+1],y[n+1];

for(int i=1;i<=n;i++){

cin>>x[i]>>y[i];

}

int d;

cin>>d;

int ans=0;

for(int i=1;i<=n;i++){

int st=x[i]+y[i];

if(st>=c){

continue;

}

st+=min(d,a-x[i]);

if(st>=c){

ans++;

}

}

cout<

}

int main (){

ios::sync_with_stdio(0);

cin.tie(0);

cout.tie(0);

int t=1;

// cin>>t;

while(t--){

solve();

}

return 0;

}

L.龙之研习

思路：

二分答案，减去闰年的天数

代码：

#include

using namespace std;

typedef long long ll;

#define endl '\n'

#define int long long

int n,k;

bool ck(__int128 x)

{

__int128 sum=0;

for(__int128 i=4;i<=x;)

{

sum+=x/i-x/(25*i);

i*=100;

}

return x-sum>=k;

}

void solve()

{

cin>>k;

k+=1533;

int l=1;

int r=2e18;

while(l<=r)

{

int mid=l+r>>1;

if(ck(mid)) r=mid-1;

else l=mid+1;

}

cout<

}

signed main()

{

ios::sync_with_stdio(0);

cin.tie(0);

cout.tie(0);

int t=1;

cin>>t;

while(t--)

{

solve();

}

return 0;

}

M.盲盒谜题

思路：

超级大模拟

代码：

/*

Problem: 2024 CCPC Liaoning Provincial Contest/M

Author: Core_65536

Last_Update: 2024-11-5

*/

#include

using namespace std;

#define endl '\n'

const pair loc[11] = { // 每一号宫格的坐标

{0,0}, {2,2},{1,1},{1,2},

{1,3},{2,1},{2,3},

{3,1},{3,2},{3,3}

};

map,int> col = { // 每个坐标的宫格号

{{2,2},1}, {{1,1},2}, {{1,2},3},

{{1,3},4}, {{2,1},5}, {{2,3},6},

{{3,1},7}, {{3,2},8}, {{3,3},9}

};

const vector>> dir = { // 已经排好序的8种情况的比较坐标

{{1,1},{2,2},{3,3}}, //1 2 9

{{1,2},{2,2},{3,2}}, //1 3 8

{{1,3},{2,2},{3,1}}, //1 4 7

{{2,1},{2,2},{2,3}}, //1 5 6

{{1,1},{1,2},{1,3}}, //2 3 4

{{1,1},{2,1},{3,1}}, //2 5 7

{{1,3},{2,3},{3,3}}, //4 6 9

{{3,1},{3,2},{3,3}} //7 8 9

};

void solve(){

// t:luck

int n,m,k,t; cin>>n>>m>>k>>t;

queue a; // 沸羊羊的盲盒队列

queue got; // 美羊羊获得的盲盒队列

int chess[4][4]; memset(chess,-1,sizeof(chess)); // 棋盘

map ans; // 每个盲盒获得的数量

int res = 0; // 缺少的盲盒数量

for(int i=1;i<=k;i++){ // 输入沸羊羊的盲盒队列

int x; cin>>x;

a.push(x);

}

for(int i=0;i

got.push(a.front());

a.pop();

}

while(1){ //游戏循环

//Step 1 放置盲盒

int ok = 0,DidSth = 0; // ok:是否拆出隐藏款 DidSth:是否有操作

for(int i=1;i<=9&&(!got.empty());i++){ // 遍历每一个宫格

if(chess[loc[i].first][loc[i].second] != -1){ // 如果宫格已经有盲盒则跳过

continue;

}

DidSth = 1; // 有操作

int x = got.front(); got.pop(); // 美羊羊取出一个盲盒

chess[loc[i].first][loc[i].second] = x; // 放入宫格

if(x == t){ // 如果是幸运款

if(!a.empty()){ // 如果沸羊羊还有盲盒

got.push(a.front()); // 奖励一个盲盒

a.pop();

}else{ // 沸羊羊没有盲盒

res ++; // 缺少的盲盒数量+1

}

}else if(x == 0){ // 如果是隐藏款

if(!a.empty()){

got.push(a.front());

a.pop();

}else{

res ++;

}

ans[x] ++ ; // 更新答案

chess[loc[i].first][loc[i].second] = -1;

ok = 1;

break;

}

}

if(ok){ // 如果拆出隐藏款则跳过后面的步骤

continue;

}

//Step 2 判断是否9个盲盒均不同

unordered_map count;

for(int i=1;i<=3;i++)

for(int j=1;j<=3;j++)

if(chess[i][j] != -1) // 排除空格

count[chess[i][j]] ++ ;

if(count.size() == 9){ // 9个盲盒均不同

DidSth = 1;

ans[chess[loc[1].first][loc[1].second]] ++; // 更新答案

chess[loc[1].first][loc[1].second] = -1;

}

//Step 3 按顺序检查8种三连珠情况

int UseSpeFlag = 0; // 是否利用到特殊格

vector> process; // 存储有几种三连珠情况 & 每一种情况的三个盲盒的宫格号

for(int i=0;i<8;i++){

int x1[3],y1[3];

for(int j=0;j<3;j++){ // 存入当前需要比较的坐标

x1[j] = dir[i][j].first;

y1[j] = dir[i][j].second;

}

// 比较三个盲盒是否相同 & 排除空格

if(chess[x1[0]][y1[0]]==chess[x1[1]][y1[1]]&&chess[x1[1]][y1[1]]==chess[x1[2]][y1[2]]&&chess[x1[0]][y1[0]]!=-1){

DidSth = 1;

vector cnt;

for(int j=0;j<3;j++){

cnt.push_back(col[{x1[j],y1[j]}]); // 存入宫格号

}

process.push_back(cnt); // 存入当前三连珠情况

}

}

//Start Process

for(auto i:process){ // 遍历每一种三连珠情况

int x1[3],y1[3];

for(int j=0;j<3;j++){ // 存入当前需要处理的坐标

x1[j] = loc[i[j]].first;

y1[j] = loc[i[j]].second;

}

// 排除已经处理过变成空格的宫格

if(chess[x1[0]][y1[0]]!=-1&&chess[x1[1]][y1[1]]!=-1&&chess[x1[2]][y1[2]]!=-1){

for(int j=0;j<5;j++){ // 发放奖励盲盒

if(!a.empty()){

got.push(a.front());

a.pop();

}else{

res ++;

}

}

for(int j=0;j<3;j++){ // 遍历三连珠的三个盲盒

if(i[j] == 1){ // 如果是特殊格

UseSpeFlag = 1;

continue;

}else{ // 不是特殊格

ans[chess[x1[j]][y1[j]]] ++; // 更新答案

chess[x1[j]][y1[j]] = -1;

}

}

}

}

//Step 4 顺序检查任意两种盲盒是否相同

for(int i=1;i<=9;i++){

for(int j=i;j<=9;j++){

if(j <= i) continue; // 遍历宫格号以做到顺序遍历

int x1 = loc[i].first, y1 = loc[i].second;

int x2 = loc[j].first, y2 = loc[j].second;

// 如果两个盲盒相同 & 不是空格

if(chess[x1][y1] == chess[x2][y2] && chess[x1][y1] != -1){

DidSth = 1;

if(i == 1){ // 如果第一个利用到特殊格

UseSpeFlag = 1;

if(!a.empty()){

got.push(a.front());

a.pop();

}else{

res ++;

}

ans[chess[x2][y2]] ++; // 更新答案

chess[x2][y2] = -1;

continue;

}

if(j == 1){ // 如果第二个利用到特殊格

UseSpeFlag = 1;

if(!a.empty()){

got.push(a.front());

a.pop();

}else{

res ++;

}

ans[chess[x1][y1]] ++; // 更新答案

chess[x1][y1] = -1;

continue;

}

// 如果没利用到特殊格

if(!a.empty()){

got.push(a.front());

a.pop();

}else{

res ++;

}

ans[chess[x1][y1]] += 2; // 更新答案

chess[x1][y1] = chess[x2][y2] = -1;

}

}

}

//Step 5 判断是否利用到特殊格

if(UseSpeFlag == 1){

DidSth = 1;

ans[chess[2][2]] ++; // 更新答案

chess[2][2] = -1;

}

//Step 6 如果没有操作游戏结束

if(!DidSth){

break;

}

int Judge0Flag = 0; // 判断是否清台

for(int i = 1 ;i <= 9 ; i++){

if(chess[loc[i].first][loc[i].second] == -1)

Judge0Flag ++;

}

if(Judge0Flag == 9){ // 如果清台

for(int i=0;i<10;i++){ // 发放奖励盲盒

if(!a.empty()){

got.push(a.front());

a.pop();

}else{

res ++;

}

}

}

}

// 游戏结束, 清理棋盘

for(int i=1;i<=9;i++){

if(chess[loc[i].first][loc[i].second] != -1){

ans[chess[loc[i].first][loc[i].second]] ++;

chess[loc[i].first][loc[i].second] = -1;

}

}

for(int i = 0;i <= m;i ++){ // 输出每一种盲盒获得的数量

cout<

}

if(res != 0){ // 输出缺少的盲盒数量

cout<<"Unhappy! "<

}

return ;

}

int main(){

ios::sync_with_stdio(0);

cin.tie(0); cout.tie(0);

int t=1; // cin>>t;

while(t--){

solve();

}

return 0;

}