2020年“远光杯”粤澳计算机程序设计大赛网络资格赛 题解1
由于题目太多分成两篇文章总结，这一篇是后 11 至 20题。
加上代码头文章太长，所以把模板放在最后。
如果有什么讲的不清楚的欢迎留言私信交流~
文章目录
- K . 项目管理
- L . 捕鱼达人
- M . 排除危险
- N . 图像编码问题
- O . 军训值日生
- P . 今天图书馆开了没？
- Q . 小明的体育课
- R . 孤独的字符串
- S . 鲍勃的输入法
- T . 一起做课件
- ends: 代码头
K . 项目管理
思路：贪心，把用时间长的安排在前面，这样在他在工作的时间可以去给其他人安排。
代码：
struct node{
ll x,y;
}a[manx];
bool cmp(node a,node b){
return a.y>b.y;
}
int main(){
ll n; cin>>n;
for(int i=1;i<=n;i++)
cin>>a[i].x>>a[i].y;
ll ans=0,cnt=0;
sort(a+1,a+1+n,cmp);
for(int i=1;i<=n;i++){
cnt+=a[i].x;
ans=max(ans,cnt+a[i].y);
}
cout<<"Project "<<n<<": "<<ans<<endl;
return 0;
}
L . 捕鱼达人
思路：
- 本来是想用LIS的，但是发现顺序不能改变，所以就没办法了。
- 考虑优化求该位置前的最大值，用线段树优化+ dp。
- 以魅力值的值域作为线段树的结点，dp数组维护以 i 结尾的序列的价值最大和。
- 遍历的时候把枚举的元素的价值加入到该魅力值的结点，在遍历的时候更新最大值，也就是取max，由于可以从左到右和从右到左，所以这个过程重复两次。
代码：
const int manx=2e5+5;
ll yz[manx],val[manx];
ll dp[manx];
struct node{
ll l,r,x;
}a[manx*5];
void build(ll k,ll l,ll r){
a[k].l=l,a[k].r=r;
if(l==r){
a[k].x=0; return ;
}
ll mid= l+r>>1;
build(kl,l,mid); build(kr,mid+1,r);
a[k].x=max(a[kl].x,a[kr].x);
}
ll query(ll k,ll l,ll r){
if(a[k].l>=l&&a[k].r<=r){
return a[k].x;
}
ll mid= (a[k].l+a[k].r)>>1;
ll ans=0;
if(l<=mid) ans=max(ans,query(kl,l,r));
if(r>mid) ans=max(ans,query(kr,l,r));
return ans;
}
void update(ll k,ll pos,ll v){
if(a[k].l==a[k].r){
a[k].x=v;
return ;
}
ll mid= (a[k].l+a[k].r)>>1;
if(pos<=mid) update(kl,pos,v);
else update(kr,pos,v);
a[k].x=max(a[kl].x,a[kr].x);
}
int main(){
io;
ll p; cin>>p; ll cnt=0;
while(p--){
ll n,x,ans=0,dd=0; cin>>n;
for(int i=1;i<=n;i++){
cin>>x;
yz[i]=x%10000; yz[i]+=60001;
val[i]=x/10000;
if(yz[i]>dd) dd=yz[i];
}
build(1,1,dd);
for(int i=1;i<=n;i++){
ll mx=query(1,1,yz[i]);
dp[i]=mx+val[i];
ans=max(ans,dp[i]);
update(1,yz[i],dp[i]);
}
build(1,1,dd);
for(int i=n;i>=1;i--){
ll mx=query(1,1,yz[i]);
dp[i]=mx+val[i];
ans=max(ans,dp[i]);
update(1,yz[i],dp[i]);
}
cout<<"Case #"<<++cnt<<": ";
cout<<ans<<endl;
}
return 0;
}
M . 排除危险
思路： 根据题意模拟就可以，让化学物品ans！=元素种类cnt。
代码：
ll cnt;
map<ll,ll>vis;
int main(){
ll x,y; ll ans=0,res=0,n=0;
while(cin>>x){
if(x==-1) break;
cin>>y;
n++;
res=0;
if(vis[x]==0) res++; vis[x]++;
if(vis[y]==0) res++; vis[y]++;
ans++; cnt+=res;
if(ans==cnt){
ans--; cnt-=res;
vis[x]--; vis[y]--;
}
// cout<<ans<<" "<<cnt<<endl<<endl;
}
cout<<n-ans<<endl;
return 0;
}
N . 图像编码问题
思路： 根据题意模拟，注意合并s1和s2之后要注意去掉前缀0 。
代码：
struct node{
ll x,val;
}a[manx];
ll k=0;
bool cmp(node a,node b){
return a.val<b.val;
}
void pd(ll l,ll r){
string sl="",sr="";
do{
if(l&1) sl+="1";
else sl+="0";
l/=2;
}while(l);
do{
if(r&1) sr+="1";
else sr+="0";
r/=2;
}while(r);
while(sl.size()<sr.size()) sl+="0";
while(sr.size()<sl.size()) sr+="0";
// cout<<sl<<" "<<sr<<endl;
reverse(sl.begin(),sl.end());
reverse(sr.begin(),sr.end());
string s="";
for(int i=0;i<sl.size();i++)
s+=sl[i],s+=sr[i];
ll p=0;
for(int i=0;i<s.size();i++)
if(s[i]=='0') p++;
else break;
s.erase(0,p);
ll x=1,ans=0;
if(s.size()==0){
a[k].val=ans;
return ;
}
for(int i=s.size()-1;i>=0;i--){
if(s[i]=='1') ans+=x;
x<<=1;
}
a[k].val=ans;
// cout<<sl<<" "<<sr<<" "<<s<<" "<<ans<<endl;
}
int main(){
ll n; cin>>n;
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++){
cin>>a[++k].x;
pd(i-1,j-1);
}
sort(a+1,a+1+k,cmp);
for(int i=1;i<=k;i++){
ll cnt=1,p=i+1;
while(p<=k&&a[i].x==a[p].x) cnt++,p++;
if(p!=k+1&&i!=k) cout<<a[i].x<<","<<cnt<<" ";
else cout<<a[i].x<<","<<cnt;
i=i+cnt-1;
}
return 0;
}
O . 军训值日生
思路：区间dp，s维护1~i 的物品和，dp维护l~r的消耗，不会的可以去做一下合并石子。
代码：
ll a[manx],s[manx]; ll dp[manx][manx];
int main(){
ll n;
while(cin>>n){
ll ans=0;
memset(dp,inf,sizeof(dp));
s[0]=0;
for(int i=1;i<=n;i++) cin>>a[i],dp[i][i]=0,s[i]=s[i-1]+a[i];
for(int len=2;len<=n;len++){
for(int i=1;i<=n;i++){
int j=i+len-1;
if(j>n) continue;
for(int k=i;k<=j;k++){
dp[i][j]=min(dp[i][j],dp[i][k]+dp[k+1][j]+(s[k]-s[i-1])*(s[j]-s[k]));
}
}
}
cout<<dp[1][n]<<endl;
}
return 0;
}
P . 今天图书馆开了没？
思路： d p [ i ] [ j ] dp[i][j] dp[i][j]维护第 i 天去第 j 个图书馆的最大值，只有两种情况：
- 当天有开图书馆且前一天该图书馆没开，有：
d p [ i ] [ j ] = m a x ( d p [ i ] [ j ] , d p [ i − 1 ] [ k ] + 1 ) dp[i][j]=max(dp[i][j],dp[i-1][k]+1) dp[i][j]=max(dp[i][j],dp[i−1][k]+1) - 其余情况都是：
d p [ i ] [ j ] = m a x ( d p [ i ] [ j ] , d p [ i − 1 ] [ k ] ) dp[i][j]=max(dp[i][j],dp[i-1][k]) dp[i][j]=max(dp[i][j],dp[i−1][k])
代码：
const int manx=100000+5;
ll a[manx][5],dp[manx][5];
int main(){
io;
ll n; cin>>n;
for(int i=1;i<=n;i++){
for(int j=1;j<=4;j++) cin>>a[i][j];
}
for(int j=1;j<=4;j++) dp[1][j]=a[1][j];
for(int i=2;i<=n;i++){
for(int j=1;j<=4;j++){
if(a[i][j])
for(int k=1;k<=4;k++){
if(j==k&&a[i-1][j]) dp[i][j]=max(dp[i][j],dp[i-1][j]);
else dp[i][j]=max(dp[i][j],dp[i-1][k]+1);
}
else for(int k=1;k<=4;k++) dp[i][j]=max(dp[i][j],dp[i-1][k]);
}
}
ll ans=0;
for(int i=1;i<=4;i++)
ans=max(ans,dp[n][i]);
cout<<ans<<endl;
// cout<<endl;
return 0;
}
Q . 小明的体育课
思路：经典爬楼梯~dp[i]维护到达i点的方案，只能走1/2步，所以由前两个转移。
代码：
ll dp[50];
int main(){
ll n; io; dp[1]=1; dp[2]=2;
for(int i=3;i<=35;i++) dp[i]=dp[i-1]+dp[i-2];
//for(int i=3;i<=35;i++) cout<<dp[i]<<endl;
while(cin>>n){
cout<<dp[n]<<endl;
}
return 0;
}
R . 孤独的字符串
思路：
-
用dp[i][j][1/0]维护前i个元素状态为j是否存在aba子串的方案数
因为只有两个字符，所以把a看成0，b看成1
状态只有4(2^2)个 aa为0 ab为1 ba为2 bb为3 -
递推过程：
考虑8次 四个状态* （合法+不合法）
例如
00 可以由 0 00 1 00 推出
01 可以由 1 01 0 01 推出
就是在前面加上0和1两种
但是要注意合法性
比如说 dp[i][1][0]
本来是dp[i][1][0]+=dp[i-1][0][0] + dp[i-1][2][0]
注意 2的二进制位为10 恒定合法
所以只能写成 dp[i][1][0]+=dp[i-1][0][0] -
再比如说
dp[i][0][0] += dp[i-1][0][0]+dp[i-1][2][0]
这个的意思就是前i位的后两位 为 00 的状态且不合法的个数
它由什么递推？肯定前一位是0 再前一位可以是0也可以是1
就是 dp[i-1][0(00)][0]+dp[i-1][1(10)][0]
代码：
t = int(input())
dp = [[[0 for i in range(3)] for i in range(5)] for i in range(110)]
dp[2][0][0] = 1 # aa
dp[2][1][1] = 1 # ab
dp[2][2][0] = 1 # ba
dp[2][3][0] = 1 # bb
for i in range(105):
dp[i][0][0] += dp[i-1][0][0]+dp[i-1][2][0]
dp[i][1][0] += dp[i-1][0][0]
dp[i][2][0] += dp[i-1][1][0]+dp[i-1][3][0]
dp[i][3][0] += dp[i-1][1][0]+dp[i-1][3][0]
#
dp[i][0][1] += dp[i-1][0][1]+dp[i-1][2][1]
dp[i][1][1] += dp[i-1][0][1]+dp[i-1][2][1]+dp[i-1][2][0]
dp[i][2][1] += dp[i-1][1][1]+dp[i-1][3][1]
dp[i][3][1] += dp[i-1][1][1]+dp[i-1][3][1]
for i in range(t):
x = int(input())
ans = 0
if(x == 1 or x == 2):
print(x)
else:
for i in range(4):
ans += dp[x][i][1]
ans += dp[x][2][0]
print(int(ans))
S . 鲍勃的输入法
思路：字典树+dfs 但是写挂了。 2020.4.26 订正：
- 字典树的查找过程其实就是按字典序顺序查找的，所以标记字符串的结点位置和每个结点对应的字符串，然后遍历输出即可，当输出达到50个就return 。
代码：
const int manx=100000+5;
struct node{
ll son[26],cnt;
bool flag;
}a[800000];
ll id,cnt;
map<string,ll>vis;
map<ll,string>ans;
void add(string s){
int n=s.size();
ll u=0;
for(int i=0;i<n;i++){
char x=s[i];
ll v= x-'a';
if(!a[u].son[v]) a[u].son[v]=++id;
u=a[u].son[v];
}
a[u].flag=true; vis[s]=u; ans[u]=s;
}
void dfs(ll u){
if(cnt>=50) return ;
if(a[u].flag) cout<<ans[u]<<endl,cnt++;
for(int i=0;i<26;i++){
ll v=a[u].son[i];
if(v)
dfs(v);
}
}
ll query(string s){
int n=s.size(); ll u=0;
for(int i=0;i<n;i++){
ll v=s[i]-'a';
if(!a[u].son[v]) return -1;
u=a[u].son[v];
}
return u;
}
int main(){
ll n; cin>>n;
for(int i=1;i<=n;i++){
string s; cin>>s;
if(!vis[s]) add(s);
}
ll m; cin>>m;
while(m--){
cnt=0;
string s; cin>>s;
if(!vis[s]) cout<<s<<endl,++cnt;
ll f=query(s);
if(f==-1) add(s);
else dfs(f);
}
return 0;
}
T . 一起做课件
思路：
代码：
ends: 代码头
#include<bits/stdc++.h>
#define mp make_pair
#define pb push_back
#define ll long long
#define fi first
#define se second
#define inf 0x3f3f3f3f
#define io std::ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
using namespace std;
inline ll read(){ll s=0,w=1;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}
while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar();return s*w;}
void put1(){ puts("Yes") ;}void put2(){ puts("No") ;}void put3(){ puts("-1"); }
ll qp(ll a,ll b, ll p){ll ans = 1;while(b){if(b&1){ans = (ans*a)%p;--b;}a =
(a*a)%p;b >>= 1;}return ans%p;}
const int mo=998244353; const int mod=1000000007;
const int manx=1e6+5;
int main(){
return 0;
}
