当前位置:网站首页>2019河北省大学生程序设计竞赛部分题题解
2019河北省大学生程序设计竞赛部分题题解
2022-08-10 19:12:00 【可然冫】
B. Icebound and Sequence
快速乘&快速幂&逆元
了解逆元
#include<bits/stdc++.h>
using namespace std;
ll mod,q,n;
ll ksc(ll x,ll y)
{
ll ans=0;
while(y)
{
if(y&1) ans=(ans+x)%mod;
x=2*x%mod;
y/=2;
}
return ans;
}
ll ksm(ll x,ll y)
{
ll ans=1;
while(y)
{
if(y&1)ret=ksc(ret,x)%mod;
x=ksc(x,x)%mod;
y/=2;
}
return ret;
}
int main()
{
int t;
scanf("%d",&t);
while(t--)
{
scanf("%lld%lld%lld",&q,&n,&mod);
mod=(q-1)*mod;
ll ans=(fp(q,n+1)-q+mod)%mod/(q-1);
printf("%lld\n",ans);
}
}
C. 分治
区间DP,逆向思考。
#include<bits/stdc++.h>
using namespace std;
int dp[110][110],cost[110],T,n;
int main()
{
cin>>T;
while(T--)
{
cin>>n;
memset(dp,0x3f,sizeof(dp));
for(int i=1;i<=n;i++)
scanf("%d",&cost[i]),dp[i][i]=0;
for(int len=2;len<=n;len++)
{
for(int l=1;l+len-1<=n;l++)
{
int r=l+len-1;
for(int k=l;k<=r;k++)
{
if(k==l) dp[l][r]=min(dp[l][r],dp[k+1][r]+cost[l]*(r-l));
else if(k==r) dp[l][r]=min(dp[l][r],dp[l][k-1]+cost[r]*(r-l));
else dp[l][r]=min(dp[l][r],dp[l][k-1]+dp[k+1][r]+cost[k]*(r-l));
}
}
}
cout<<dp[1][n]<<endl;
}
return 0;
}
E. Paper Plane Fly Away
树状数组求逆序对。博客
#include<bits/stdc++.h>
using namespace std;
const int N=200010;
int n,pos[N],love[N],seat[N],c[N],ans[N];
int lowbit(int x)
{
return x&(-x);
}
void add(int p)
{
for(int i=p;i<=n;i+=lowbit(i))
c[i]++;
}
int get(int p)
{
int sum=0;
for(int i=p;i;i-=lowbit(i))
sum+=c[i];
return sum;
}
int main()
{
cin>>n;
for(int i=1;i<=n;i++)
{
int x;
scanf("%d%d",&x,&love[i]);
pos[x]=i;
}
for(int i=1;i<=n;i++)
seat[i]=pos[love[i]];
for(int i=n;i;i--)
{
ans[i]+=get(seat[i]);
add(seat[i]);
}
memset(c,0,sizeof(c));
for(int i=1;i<=n;i++)
{
ans[i]+=get(n)-get(seat[i]);
add(seat[i]);
printf("%d\n",ans[i]);
}
return 0;
}
J. 舔狗
拓扑排序,从入度小的地方开始(应该算是一种贪心?),一对点一对点地拆。
#include<bits/stdc++.h>
using namespace std;
const int N=1e6+10;
int n,a[N],ind[N],vis[N];
struct node
{
int x,p;
};
bool operator < (node a,node b){
return a.p>b.p;}
priority_queue<node> q;
int main()
{
cin>>n;
for(int i=1;i<=n;i++)
scanf("%d",&a[i]),ind[a[i]]++;
for(int i=1;i<=n;i++)
q.push({
i,ind[i]});
while(q.size())
{
node u=q.top();
q.pop();
if(vis[u.x]||vis[a[u.x]]) continue;
n-=2;
vis[u.x]=vis[a[u.x]]=1;
int now=a[a[u.x]];
ind[now]--;
q.push({
now,ind[now]});
}
cout<<n;
return 0;
}
L. smart robot
从0开始往上暴力搜索,本以为会TLE却没有,或许答案必然在一个较小的范围内是可证的?
#include<bits/stdc++.h>
using namespace std;
int mp[100][100],n,num[100];
int dx[4]={
0,-1,0,1};
int dy[4]={
1,0,-1,0};
struct node
{
int x,y,step;
};
bool bfs(int x)
{
int len=0;
if(!x) num[++len]=1;
while(x)
{
num[++len]=x%10;
x/=10;
}
queue<node>q;
for(int i=1;i<=n;i++)
for (int j=1;j<=n;j++)
if(mp[i][j]==num[1])
q.push(node{
i,j,1});
while(!q.empty())
{
node temp=q.front();
q.pop();
if(temp.step==len) return true;
for(int i=0;i<4;i++)
{
int xx=temp.x+dx[i];
int yy=temp.y+dy[i];
if(xx<1||xx>n||yy<1||yy>n) continue;
if(mp[xx][yy]!=num[temp.step+1]) continue;
q.push(node{
xx,yy,temp.step+1});
}
}
return false;
}
int main()
{
cin>>n;
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
cin>>mp[i][j];
for(int i=0;;i++)
{
if(!bfs(i))
{
cout<<i<<endl;
return 0;
}
}
}
边栏推荐
- “蔚来杯“2022牛客暑期多校训练营7 F
- opengrok搭建[通俗易懂]
- 【SemiDrive源码分析】【MailBox核间通信】52 - DCF Notify 实现原理分析 及 代码实战
- IIC通信协议总结[通俗易懂]
- 不止跑路,拯救误操作rm -rf /*的小伙儿
- Redis 持久化机制
- 水溶性合金量子点纳米酶|CuMoS纳米酶|多孔硅基Pt(Au)纳米酶|[email protected]纳米模拟酶|PtCo合金纳米粒子
- (10) Sequence and deserialization of image data
- 铁蛋白颗粒Tf包载多肽/凝集素/细胞色素C/超氧化物歧化酶/多柔比星(定制服务)
- 几行深度学习代码设计包含功能位点的候选免疫原、酶活性位点、蛋白结合蛋白、金属配位蛋白
猜你喜欢
Iridium Ruthenium Alloy/Iridium Oxide Biomimetic Nanozyme | Palladium Nanozyme | GMP-Pd Nanozyme | Gold-Palladium Composite Nanozyme | Ternary Metal Pd-M-Ir Nanozyme |shell nanozyme
YOLOv3 SPP source analysis
[Go WebSocket] Your first Go WebSocket server: echo server
WCF and TCP message communication practice, c # 】 【 realize group chat function
铱钌合金/氧化铱仿生纳米酶|钯纳米酶|GMP-Pd纳米酶|金钯复合纳米酶|三元金属Pd-M-Ir纳米酶|中空金铂合金纳米笼核-多空二氧化硅壳纳米酶
【C#】WCF和TCP消息通信练习,实现群聊功能
链表应用----约瑟夫问题
Heme - gold nanoparticles (Heme - AuNP) composite nanometer enzyme | gold nanoparticles nuclear porous hollow carbon nanometer spherical shell (Au @ HCNs) nano enzyme
线性结构----链表
【知识分享】在音视频开发领域中SEI到底是个啥?
随机推荐
Linux服务器安装Redis,详细步骤。
Keras deep learning combat (17) - image segmentation using U-Net architecture
哈工大软件构造Lab3(2022)
【毕业设计】基于STM32的天气预报盒子 - 嵌入式 单片机 物联网
The servlet mapping path matching resolution
The Biotin-PEG3-Br/acid/NHS ester/alcohol/amine collection that everyone wants to share
[CNN] Brush SOTA's trick
『牛客|每日一题』岛屿数量
杭电多校七 1003-Counting Stickmen(组合数学)
Tf ferritin particles contain cisplatin / oxaliplatin / doxorubicin / methotrexate MTX / paclitaxel PTX and other drugs
YOLOv3 SPP source analysis
[教你做小游戏] 斗地主的手牌,如何布局?看25万粉游戏区UP主怎么说
GBASE 8s 高可用RSS集群搭建
QoS Quality of Service Eight Congestion Avoidance
Hangdian Multi-School Seven 1003-Counting Stickmen (Combination Mathematics)
redis如何查看key的有效期
flask生成路由的2种方式和反向生成url
服务器上行带宽和下行带宽指的是什么
洛谷 P1629 邮递员送信 (三种最短路)
赎金信问题答记