编程之美初赛第二场AB
2024-10-21 16:37:39
题目1 : 扑克牌
时间限制:2000ms
单点时限:1000ms
内存限制:256MB
描述
一副不含王的扑克牌由52张牌组成，由红桃、黑桃、梅花、方块4组牌组成，每组13张不同的面值。现在给定52张牌中的若干张，请计算将它们排成一列，相邻的牌面值不同的方案数。
牌的表示方法为XY，其中X为面值，为2、3、4、5、6、7、8、9、T、J、Q、K、A中的一个。Y为花色，为S、H、D、C中的一个。如2S、2H、TD等。
输入
第一行为一个整数T，为数据组数。
之后每组数据占一行。这一行首先包含一个整数N，表示给定的牌的张数，接下来N个由空格分隔的字符串，每个字符串长度为2，表示一张牌。每组数据中的扑克牌各不相同。
输出
对于每组数据输出一行，形如"Case #X: Y"。X为数据组数，从1开始。Y为可能的方案数，由于答案可能很大，请输出模264之后的值。
数据范围
1 ≤ T ≤ 20000
小数据
1 ≤ N ≤ 5
大数据
1 ≤ N ≤ 52
- 样例输入
-
5
1 TC
2 TC TS
5 2C AD AC JC JH
4 AC KC QC JC
6 AC AD AS JC JD KD - 样例输出
-
Case #1: 1
Case #2: 0
Case #3: 48
Case #4: 24
Case #5: 120 设dp[a][b][c][d][l]状态为当前某面值的牌只存一张的有a种，面值牌剩两张的有b种，如此类推，最后是上一个操作是对一张、两张。。。的操作。如l=3,则对三张的操作，会使得c-1,b+1。可以看到是记忆化搜索。注意的是，当上一前操作如l=3时，如果当前操作减少两张的，则应该是有（b-1）种可能，因为当前的b有一种是不能添加的，会造成相邻同面值。#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#define uLL unsigned long long
using namespace std; uLL dp[15][15][15][15][5]; int counts[15];
int sum[5];
char stin[5];
bool vis[15][15][15][15][5]; int check(char s){
if(s== 'A') return 1;
if(s== 'T') return 10;
if(s== 'J') return 11;
if(s== 'Q') return 12;
if(s== 'K') return 13;
return s-'0';
} uLL dfs(int a,int b,int c,int d,int l){
if(dp[a][b][c][d][l]) return dp[a][b][c][d][l];
if(a){
dp[a][b][c][d][l]+=dfs(a-1,b,c,d,1)*(a-(l==2?1:0));
}
if(b) dp[a][b][c][d][l]+=dfs(a+1,b-1,c,d,2)*(b-(l==3?1:0));
if(c) dp[a][b][c][d][l]+=dfs(a,b+1,c-1,d,3)*(c-(l==4?1:0));
if(d) dp[a][b][c][d][l]+=dfs(a,b,c+1,d-1,4)*d;
return dp[a][b][c][d][l];
} int main(){
int T,icase=0,n;
memset(dp,0,sizeof(dp));
scanf("%d",&T);
while(T--){
scanf("%d",&n);
memset(counts,0,sizeof(counts));
memset(sum,0,sizeof(sum));
for(int i=1;i<=n;i++){
scanf("%s",stin);
counts[check(stin[0])]++;
}
for(int i=1;i<=13;i++){
sum[counts[i]]++;
}
for(int i=1;i<=4;i++){
dp[0][0][0][0][i]=1;
}
uLL ans=dfs(sum[1],sum[2],sum[3],sum[4],0);
for(int i=1;i<=13;i++){
for(int j=1;j<=counts[i];j++)
ans*=j;
}
printf("Case #%d: %llu\n",++icase,ans);
}
return 0;
}题目2 : 攻城略地
时间限制:2000ms单点时限:1000ms内存限制:256MB描述
A、B两国间发生战争了，B国要在最短时间内对A国发动攻击。已知A国共有n个城市（城市编号1, 2, …, n），城市间有一些道路相连。每座城市的防御力为w，直接攻下该城的代价是w。若该城市的相邻城市（有道路连接）中有一个已被占领，则攻下该城市的代价为0。
除了占领城市，B国还要摧毁A国的交通系统，因而他们需要破坏至少k条道路。由于道路损毁，攻下所有城市的代价相应会增加。假设B国可以任意选择要摧毁的道路，那么攻下所有城市的最小代价是多少？
输入
第一行一个整数T，表示数据组数，以下是T组数据。
每组数据第一行包含3个整数n, m, k。
第二行是n个整数，分别表示占领城市1, 2, …, n的代价w。
接下来m行每行两个数i, j，表示城市i与城市j间有一条道路。
输出
对于每组数据输出一行，格式为"Case #X: Y"。X表示数据编号（从1开始），Y为答案。
数据范围
1 ≤ T ≤ 30
k ≤ m
0 ≤ w ≤ 108
小数据
1 ≤ n ≤ 1000
0 ≤ m ≤ 5000
大数据
1 ≤ n ≤ 106
0 ≤ m ≤ 106
- 样例输入
-
2
4 4 2
6 5 3 4
1 2
1 3
2 3
2 4
4 4 4
6 可以很明显知道，对一个连通分量，只需选择最小的一点攻克即可。那么，也可以知道，如果减少的边使连通分量变成一棵树，而边数又大于k，则只需攻克各自最小的那些点即可。否则，对于一棵树，任意减少一条边，最多增加一个连通分量。但希望把连通分量中最小值最小化，因此，把所有的点排序，从左往右，对于树，只需去掉不是最小值点的最小值的边，划分出一个连通分量即可。（代码WA，不知为何。。）#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#define LL long long
using namespace std; const int MAXN=1000150;
bool vis[MAXN],pre[MAXN];
struct Point{
int v,p;
}cities[MAXN]; int find(int x){
int r=x;
while(pre[r]!=r){
r=pre[r];
}
while(pre[x]!=x){
int t=pre[x];
pre[x]=r;
x=t;
}
return r;
} void Union(int u,int v){
int fu=find(u);
int fv=find(v);
if(fu!=fv){
pre[fu]=fv;
}
} bool cmp(Point a,Point b){
if(a.v<b.v) return true;
return false;
} int main(){
int T,n,m,k,u,v,icase=0;
scanf("%d",&T);
while(T--){
scanf("%d%d%d",&n,&m,&k);
for(int i=1;i<=n;i++){
scanf("%d",&cities[i].v);
cities[i].p=i;
pre[i]=i;
}
for(int i=1;i<=m;i++){
scanf("%d%d",&u,&v);
Union(u,v);
}
sort(cities+1,cities+1+n,cmp);
LL ans=0; int tot=0;
memset(vis,false,sizeof(vis));
for(int i=1;i<=n;i++){
int t=find(cities[i].p);
if(!vis[t]){
ans+=cities[i].v;
tot++;
vis[t]=true;
}
}
printf("Case #%d: ",++icase);
if(m-k>=n-tot){
printf("%lld\n",ans);
}
else{
k-=m-(n-tot);
memset(vis,false,sizeof(vis));
for(int i=1;i<=n&&k>0;i++){
if(!vis[pre[cities[i].p]]){
vis[pre[cities[i].p]]=true;
continue;
}
ans+=cities[i].v;
k--;
}
printf("%lld\n",ans);
}
}
}
最新文章
- python 爬虫（五）
- 聊聊SOA面向服务架构
- Linux设置ssh无密码登陆
- ios xmpp开发应用后台模式接收聊天信息处理方案
- Linux驱动设计——内存与IO访问
- 华为OJ：字符串合并处理
- 挺好看的CSS
- mysql删除、修改字段默认值
- Android开发之一个未解决的bug
- ECSHOP文件目录详解
- SecureCRT+WinSCP 共用 key pub 密钥 转换 ppk 登录ssh
- 点击<a>标签，禁止页面自动跳到顶部的解决办法
- 天气情况（思维，dp思想）
- 关于Program Size
- Linux网络管理——Linux网络命令
- UML建模技术（资料汇总）
- webapi 使用Autofac 开发经历
- 如何指定一个计划和目标——6W
- 百度编辑器 Ueditor 如何增加模板 ？
- Transformer+BERT+GPT+GPT2