大家好,又见面了,我是你们的朋友全栈君。如果您正在找激活码,请点击查看最新教程,关注关注公众号 “全栈程序员社区” 获取激活教程,可能之前旧版本教程已经失效.最新Idea2022.1教程亲测有效,一键激活。
Jetbrains全家桶1年46,售后保障稳定
-
- Prob.1 转圈游戏
找到循环节,然后快速幂。
代码:
#include<cstdio>
#include<cstring>
#include<iostream>
using namespace std;
int pos[1000005],vis[1000000];
int n,m,k,x,p,mod;
int pow(int a,int b){
int now=1;
while(b){
if(b&1) now=1ll*now*a%mod;
a=1ll*a*a%mod;
b>>=1;
}
return now;
}
int main(){
scanf("%d%d%d%d",&n,&m,&k,&x);
while(!vis[x]){
vis[x]=1; pos[mod++]=x;
x=(x+m)%n;
}
p=pow(10,k);
printf("%d",pos[p]);
return 0;
}
-
- Prob.2 火柴排队
骚操作啊。我太菜了。
首先,(由于每一列的高度互不相同),我们把每一列分别按高度从小到大的顺序给以每个元素排名,
那么最小的距离和就是 两列中相同的排名两两对应 所计算出来的值。
证明的话,可以考虑交换两个组合的元素,发现计算出的权值只会变大。
为了把相同的名次对应,
所以就是要把两个序列都从小到大排序或者都从大到小排序么?
蠢蠢的我想到了上面这个东西,但显然错了,然后我就不知道如何搞了。
正解:
其实两列的交换是等价且相互的
也就是说,我们可以只通过对第一列进行交换达到相同名次对应的目的。
所以我们映射出第一个序列的每个元素在第二个序列中的出现的位置,得到一个新的序列,
求出这个新的序列的逆序对数就是答案了。
(这个题太强辣。%%%)
代码:
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#define MAXN 100005
using namespace std;
const int mod=99999997;
int cc[MAXN],A[MAXN],B[MAXN],p[MAXN];
int n,ans;
void readwork(int *a){
for(int i=1;i<=n;i++) scanf("%d",&a[i]),cc[i]=a[i];
sort(cc+1,cc+n+1);
for(int i=1;i<=n;i++) a[i]=lower_bound(cc+1,cc+n+1,a[i])-cc;
}
void merge(int *a,int l,int r){
static int tmp[MAXN];
if(l==r) return;
int mid=(l+r)>>1;
merge(a,l,mid);
merge(a,mid+1,r);
int h=l,t=mid+1,pp=l;
while(h<=mid&&t<=r){
if(a[h]<a[t]) tmp[pp++]=a[h++];
else ans=(1ll*ans+mid-h+1)%mod,tmp[pp++]=a[t++];
}
while(h<=mid) tmp[pp++]=a[h++];
while(t<=r) tmp[pp++]=a[t++];
for(int i=l;i<=r;i++) a[i]=tmp[i];
}
int main(){
scanf("%d",&n);
readwork(A); readwork(B);
for(int i=1;i<=n;i++) p[B[i]]=i;
for(int i=1;i<=n;i++) A[i]=p[A[i]];
merge(A,1,n);
printf("%d",ans);
return 0;
}
-
- Prob.3 货车运输
先是最大生成树,保证了路径的最小值最大;
然后在倍增,进行树上RMQ就好了。
代码:
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#define INF 0x3f3f3f3f
using namespace std;
struct Cm_edge{
int u,v,w;
bool operator <(const Cm_edge &rtm){
return w>rtm.w;
}
}E[50005];
struct Lk_edge{
int to,val,next;
}e[20005];
int head[10005],fa[10005],dep[10005],stm[10005][15],stf[10005][15];
int n,m,Q,ent=2;
void add(int u,int v,int w){
e[ent]=(Lk_edge){v,w,head[u]};
head[u]=ent++;
}
void cmin(int &a,int b){
if(a>b) a=b;
}
int find(int u){
return u==fa[u]?u:fa[u]=find(fa[u]);
}
void dfs(int u,int dad,int val){
stf[u][0]=dad; stm[u][0]=val; dep[u]=dep[dad]+1;
for(int k=1;k<=14;k++){
stf[u][k]=stf[stf[u][k-1]][k-1];
if(!stf[u][k]) break;
stm[u][k]=min(stm[u][k-1],stm[stf[u][k-1]][k-1]);
}
for(int i=head[u];i;i=e[i].next){
int v=e[i].to;
if(v==dad) continue;
dfs(v,u,e[i].val);
}
}
int query(int u,int v){
if(find(u)!=find(v)) return -1;
int ans=INF;
if(dep[u]>dep[v]) swap(u,v);
for(int k=14;k>=0;k--){
if(dep[stf[v][k]]<dep[u]) continue;
cmin(ans,stm[v][k]); v=stf[v][k];
}
if(u==v) return ans;
for(int k=14;k>=0;k--){
if(stf[u][k]==stf[v][k]) continue;
cmin(ans,stm[u][k]); cmin(ans,stm[v][k]);
u=stf[u][k]; v=stf[v][k];
}
cmin(ans,stm[u][0]); cmin(ans,stm[v][0]);
return ans;
}
int main(){
scanf("%d%d",&n,&m);
for(int i=1;i<=m;i++) scanf("%d%d%d",&E[i].u,&E[i].v,&E[i].w);
sort(E+1,E+m+1);
for(int i=1;i<=n;i++) fa[i]=i;
for(int i=1,u,v,w,fu,fv;i<=m;i++){
u=E[i].u,v=E[i].v,w=E[i].w;
fu=find(u); fv=find(v);
if(fu==fv) continue;
fa[fv]=fu;
add(u,v,w); add(v,u,w);
}
memset(stm,0x3f,sizeof(stm));
dfs(1,0,INF);
scanf("%d",&Q);
for(int i=1,u,v;i<=Q;i++){
scanf("%d%d",&u,&v);
printf("%d\n",query(u,v));
}
return 0;
}
-
- Prob.4 积木大赛
思路很巧妙的题。
之前想的是维护出每层的连续的段数和。实现很麻烦,而且复杂度堪忧。
正解:
从左到右枚举,考虑当前的高度 h[i] :
(可以想象成首先我们已经搭好了1~i-1,现在告诉你需要在第i列搭 h[i]的高度)
如果 h[i-1]>=h[i] 那么显然,在我们搭好 i-1那一列是可以顺带把 第i列搭好。
如果 h[i-1]<h[i] 那么高度h[i]的下面部分,即1~h[i-1],也可以在搭 i-1那一列是可以顺带搭好。
剩下的 h[i]-h[i-1] 就要另外搭了,即贡献答案, ans+=h[i]-h[i-1]。
代码:
#include<cstdio>
#include<cstring>
#include<iostream>
using namespace std;
int main(){
int n,a=0,b=0,ans=0;
scanf("%d",&n);
for(int i=1;i<=n;i++){
a=b; scanf("%d",&b);
if(a<b) ans+=b-a;
}
printf("%d",ans);
return 0;
}
-
- Prob.5 花匠
求最大拐点数,贪心做就好。
考虑连续的三个数 a,b,c令 a<b 并且选了a,b
1).如果b<c,那么不贡献答案,并弃掉b,改为选c,这样可以使得以后下降的范围相比b更大。
2).如果b>c,那么显然该选择c,一是可以贡献一个答案(出现了拐点),二是使得以后上升的范围相比b更大。
代码:
#include<cstdio>
#include<cstring>
#include<iostream>
#include<set>
using namespace std;
int n,k,now,pre,ans=1;
int main(){
scanf("%d",&n); scanf("%d",&pre);
for(int i=2;i<=n;i++){
scanf("%d",&now);
if(now>pre&&k!=1) k=1,ans++;
if(now<pre&&k!=2) k=2,ans++;
pre=now;
}
printf("%d",ans);
return 0;
}
- Prob.6 什么“华容道”吧,没做了。
转载于:https://www.cnblogs.com/zj75211/p/7811255.html
发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/210145.html原文链接:https://javaforall.cn
【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛
【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...