【题集】51nod 基础题

news/2025/2/8 18:26:52

1000 A + B

不说话。

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 
 4 int main()
 5 {
 6     int a,b;
 7     cin>>a>>b;
 8     cout<<a+b<<endl;
 9     return 0;
10 }
View Code

 

1005 大数加法

Java BigInteger。

 1 import java.util.*;
 2 import java.math.*;
 3 
 4 public class Main{
 5     static public void main(String[] argv)
 6     {
 7         BigInteger a,b;
 8         Scanner cin = new Scanner(System.in);
 9         a=cin.nextBigInteger();
10         b=cin.nextBigInteger();
11         System.out.println(a.add(b).toString());
12         cin.close();
13     }
14 }
View Code

 

1006 最长公共子序列Lcs

dp入门题。

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 
 4 const int MAXN = 1e3+10;
 5 char str1[MAXN],str2[MAXN];
 6 int dp[MAXN][MAXN];
 7 pair<int,int> last[MAXN][MAXN],now[MAXN][MAXN];
 8 
 9 int main()
10 {
11     cin>>str1+1>>str2+1;
12     int Len1=strlen(str1+1),Len2=strlen(str2+1);
13     for(int i=0;i<MAXN;++i)
14         dp[i][0]=0,last[i][0]=now[i][0]=make_pair(i,0);
15     for(int j=0;j<MAXN;++j)
16         dp[0][j]=0,last[0][j]=now[0][j]=make_pair(0,j);
17     for(int i=1;i<=Len1;++i)
18         for(int j=1;j<=Len2;++j)
19             if(str1[i]==str2[j])
20             {
21                 dp[i][j]=dp[i-1][j-1]+1;
22                 last[i][j]=now[i-1][j-1];
23                 now[i][j]=make_pair(i,j);
24             }else
25             {
26                 if(dp[i-1][j]>=dp[i][j-1])
27                 {
28                     now[i][j]=last[i][j]=now[i-1][j];
29                     dp[i][j]=dp[i-1][j];
30                 }else
31                 {
32                     now[i][j]=last[i][j]=now[i][j-1];
33                     dp[i][j]=dp[i][j-1];
34                 }
35             }
36     string str="";
37     pair<int,int> tmp=now[Len1][Len2];
38     while(tmp.first!=0&&tmp.second!=0)
39     {
40         str=str1[tmp.first]+str;
41         tmp=last[tmp.first][tmp.second];
42     }
43     cout<<str;
44     return 0;
45 }
View Code

 

1008 N的阶乘 mod P

取模入门题。

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 
 4 int N,P;
 5 int main()
 6 {
 7     cin>>N>>P;
 8     int ans=1;
 9     for(int i=1;i<=N;++i)
10         ans=1ll*ans*i%P;
11     cout<<ans<<endl;
12     return 0;
13 }
View Code

 

1011 最大公约数GCD

内置库函数__gcd。

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 
 4 int main()
 5 {
 6     int A,B;
 7     cin>>A>>B;
 8     cout<<__gcd(A,B)<<endl;
 9     return 0;
10 }
View Code

 

1012 最小公倍数LCM

lcm(a,b)=a*b/gcd(a,b)。gcd同1011。

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 
 4 int main()
 5 {
 6     long long  A,B;
 7     cin>>A>>B;
 8     cout<<A*B/__gcd(A,B)<<endl;
 9     return 0;
10 }
View Code

 

1018 排序

内置函数sort。

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 
 4 const int maxn = 50000+100;
 5 
 6 int a[maxn];
 7 int main()
 8 {
 9     int n;
10     cin>>n;
11     for(int i=0;i<n;++i)    cin>>a[i];
12     sort(a,a+n);
13     for(int i=0;i<n;++i)    cout<<a[i]<<endl;
14     return 0;
15 }
View Code

 

1027 大数乘法

Java BigInteger。

 1 import java.util.*;
 2 import java.math.*;
 3 
 4 public class Main{
 5     static public void main(String[] argv)
 6     {
 7         BigInteger a,b;
 8         Scanner cin = new Scanner(System.in);
 9         a=cin.nextBigInteger();
10         b=cin.nextBigInteger();
11         System.out.println(a.multiply(b).toString());
12         cin.close();
13     }
14 }
View Code

 

1046 A^B Mod C

快速幂版题。

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 
 4 int main()
 5 {
 6     int a,b,p;
 7     cin>>a>>b>>p;
 8     int ans=1,now=a;
 9     while(b)
10     {
11         if(b&1) ans=1ll*ans*now%p;
12         now=1ll*now*now%p;
13         b>>=1;
14     }
15     cout<<ans<<endl;
16     return 0;
17 }
View Code

 

1049 最大子段和

裸dp。dp[i]表示右端点为i的子段的最大值，dp[i+1]=max(dp[i],0)+a[i+1]。

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 
 4 const int MAXN = 50000+100;
 5 typedef long long ll;
 6 ll A[MAXN];
 7 ll endmax,MaxAns;
 8 int main()
 9 {
10     int N;
11     cin>>N;
12     for(int i=0;i<N;++i)    cin>>A[i];
13     endmax=MaxAns=A[0];
14     for(int i=1;i<N;++i)    endmax=max(endmax,0ll)+A[i],MaxAns=max(MaxAns,endmax);
15     cout<<MaxAns;
16     return 0;
17 }
View Code

 

1058 N的阶乘的长度

数k十进制下长度为log10(k)+1。log(N!)=log(1)+log(2)+···+log(N)。

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 
 4 int main()
 5 {
 6     int N;
 7     long double ans=0.0;
 8     cin>>N;
 9     for(int i=1;i<=N;++i)
10         ans+=log10(i);
11     cout<<(long long)floor(ans)+1<<endl;
12     return 0;
13 }
View Code

 

1066 Bash游戏

Bash博弈版题。

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 
 4 int main()
 5 {
 6     int T;
 7     int N,K;
 8     cin>>T;
 9     while(T--)
10     {
11         cin>>N>>K;
12         if(N%(K+1)) cout<<"A"<<endl;
13         else cout<<"B"<<endl;
14     }
15     return 0;
16 }
View Code

 

1069 Nim游戏

Nim博弈版题。

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 
 4 int main()
 5 {
 6     int N;
 7     cin>>N;
 8     int d;
 9     int ans=0;
10     while(N--)
11     {
12         cin>>d;
13         ans^=d;
14     }
15     if(ans) cout<<"A"<<endl;
16     else cout<<"B"<<endl;
17     return 0;
18 }
View Code

 

1072 威佐夫游戏

Wythoff博弈版题。

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 const int maxn = 2000000+100;
 4 bool vis[maxn<<2];
 5 map<pair<int,int> ,bool> Map;
 6 #define mp make_pair
 7 int main()
 8 {
 9     int T,A,B;
10     cin>>T;
11     int nxt=0;
12     for(int k=0;nxt<maxn;++k)
13     {
14         Map[mp(nxt,nxt+k)]=true;
15         if(nxt+k<maxn)  vis[nxt+k]=true;
16         vis[nxt]=true;
17         while(nxt<maxn&&vis[nxt]) nxt++;
18     }
19     while(T--)
20     {
21         cin>>A>>B;
22         if(A>B) swap(A,B);
23         if(Map.count(mp(A,B)))  cout<<"B"<<endl;
24         else cout<<"A"<<endl;
25     }
26     return 0;
27 }
View Code

 

1081 子段求和

裸前缀和。

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 const int maxn = 2000000+100;
 4 bool vis[maxn<<2];
 5 map<pair<int,int> ,bool> Map;
 6 #define mp make_pair
 7 int main()
 8 {
 9     int T,A,B;
10     cin>>T;
11     int nxt=0;
12     for(int k=0;nxt<maxn;++k)
13     {
14         Map[mp(nxt,nxt+k)]=true;
15         if(nxt+k<maxn)  vis[nxt+k]=true;
16         vis[nxt]=true;
17         while(nxt<maxn&&vis[nxt]) nxt++;
18     }
19     while(T--)
20     {
21         cin>>A>>B;
22         if(A>B) swap(A,B);
23         if(Map.count(mp(A,B)))  cout<<"B"<<endl;
24         else cout<<"A"<<endl;
25     }
26     return 0;
27 }
View Code

 

1118 机器人走方格

C(m+n-2,m-1)。代码用的dp。

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 
 4 const int maxn = 1000+100;
 5 typedef long long ll;
 6 const ll MOD = 1000000007;
 7 int C[maxn][maxn];
 8 int main()
 9 {
10     C[1][1]=1;
11     for(int i=1;i<maxn;++i)
12         for(int j=1;j<maxn;++j)
13             if(i+j!=2)
14                 C[i][j]=(C[i-1][j]+C[i][j-1])%MOD;
15     int m,n;
16     cin>>m>>n;
17     cout<<C[m][n]<<endl;
18     return 0;
19 }
View Code

 

1212 无向图最小生成树

最小生成树版题。

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 
 4 const int maxn = 1000+10;
 5 const int maxe = 50000+10;
 6 int Set[maxn];
 7 struct Edge{
 8     int u,v,w;
 9 }edge[maxe];
10 bool cmp(Edge a,Edge b)
11 {
12     return a.w<b.w;
13 }
14 int Find(int u)
15 {
16     return (Set[u]<0)?u:(Set[u]=Find(Set[u]));
17 }
18 bool Union(int u,int v)
19 {
20     if((u=Find(u))==(v=Find(v)))    return false;
21     if(Set[u]>Set[v])   swap(u,v);
22     Set[u]+=Set[v];
23     Set[v]=u;
24     return true;
25 }
26 int main()
27 {
28     ios::sync_with_stdio(false);
29     int tot,n,e;
30     cin>>n>>e;
31     memset(Set,-1,sizeof Set);
32     for(int i=0;i<e;++i)
33     {
34         cin>>edge[i].u>>edge[i].v>>edge[i].w;
35     }
36     sort(edge,edge+e,cmp);
37     int cnt=1;
38     int i=0;
39     int ans=0;
40     while(cnt<n&&i<e)
41     {
42         if(Union(edge[i].u,edge[i].v))    cnt++,ans+=edge[i].w;
43         ++i;
44     }
45     cout<<ans<<endl;
46     return 0;
47 }
View Code

 

1459 迷宫游戏

最短路版题。

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 struct vnode{
 4     int u,v,w;
 5     int p;
 6     bool operator < (const vnode& x) const
 7     {
 8         return (w>x.w)||(w==x.w&&p<x.p);
 9     }
10     vnode(int u,int v,int w,int p):u(u),v(v),w(w),p(p){;}
11 };
12 priority_queue<vnode> pq;
13 const int maxn = 500+3;
14 bool vis[maxn];
15 const int maxe = maxn*maxn;
16 int u[maxe],v[maxe],t[maxe],w[maxe];
17 int Edge[maxn],pre[maxe],nxt[maxe],tot=0;
18 int po[maxn];
19 void add(int _u,int _v,int _t,int _w)
20 {
21     nxt[tot]=Edge[_u];
22     if(Edge[_u]!=-1)    pre[Edge[_u]]=tot;
23     Edge[_u]=tot;
24     u[tot]=_u,v[tot]=_v,t[tot]=_t,w[tot]=_w;
25     tot++;
26 }
27 int main()
28 {
29     int n,m,a,b;
30     ios::sync_with_stdio(false);
31     cin>>n>>m>>a>>b;
32     memset(Edge,-1,sizeof Edge);
33     for(int i=0;i<n;++i)   cin>>po[i];
34         int _u,_v,_t;
35     for(int i=0;i<m;++i)
36     {
37         cin>>_u>>_v>>_t;
38         add(_u,_v,_t,po[_v]);
39         add(_v,_u,_t,po[_u]);
40     }
41     pq.push(vnode(-1,a,0,po[a]));
42     int ansp=po[a],anst=0;
43     int now=0;
44     while(!pq.empty()&&!vis[b])
45     {
46         vnode tmp=pq.top();
47         pq.pop();
48        // cout<<tmp.u<<" "<<tmp.v<<" "<<tmp.w<<" "<<tmp.p<<endl;
49         if(vis[tmp.v])  continue;
50         vis[tmp.v]=true;
51         anst=tmp.w;
52         ansp=tmp.p;
53         now=Edge[tmp.v];
54         while(now!=-1)
55         {
56             pq.push(vnode(tmp.v,v[now],tmp.w+t[now],tmp.p+w[now]));
57             now=nxt[now];
58         }
59     }
60     cout<<anst<<" "<<ansp;
61     return 0;
62 }
View Code

 

转载于:https://www.cnblogs.com/scidylanpno/p/9191085.html


http://www.niftyadmin.cn/n/4557691.html

相关文章

求C语言运行环境下载

求C语言运行环境下载

||| 学习一门语言尤其是初学 tc编译器最经典了... ||| http://www.skycn.com/soft/8959.html这个是下载的地址 &#xff5e; 这样不至于使你离开软件什么都想不起来~ ||| DEV c 和VC6.0 都行 上网上搜一下devc凡是能编c的都能编c ||| c语言的话 习惯于使用txt文本誊写 养成良好…
阅读更多...
c语言软件怎么下载

c语言软件怎么下载

也在用这个.. http://down.juntuan.net/gzjt1999mmm/loveword/Microsoft.rar ||| 我用的是DEV-c4.9.9.2 你要要的话 我发给你呀QQ781920613 ||| 建议用 vc 6.0 如果是想考级的话 现在考试也是要求在这个环境下需要的换 可以留下邮箱 我传给你 我推荐这个 也支持C语言的 在windo…
阅读更多...
Java设计模式之行为型-中介者模式（UML类图+案例分析）

Java设计模式之行为型-中介者模式（UML类图+案例分析）

目录 一、基础概念 二、UML类图 三、角色设计 四、案例分析 五、总结 一、基础概念 中介者模式的核心思想是引入一个中介者对象&#xff0c;来封装和管理对象之间的交互关系。 对象之间不再直接交互&#xff0c;而是通过中介者间接交互。这样可以减少对象之间的依赖&…
阅读更多...
SpringMVC无法找到/实例化Controller IDEA中有图标可以点进去

SpringMVC无法找到/实例化Controller IDEA中有图标可以点进去

Tomcat启动正常Maven项目查看Maven项目中build标签下是否有resources标签&#xff0c;如果有则去掉或者把相应的资源的路劲都写上去&#xff0c;如果只写了下面的其中一个&#xff0c;那么会只包含那一个,详情请百度resources标签具体信息 <resources><resource>&l…
阅读更多...
CSS 解决方案

CSS 解决方案

1. 伪元素&#xff1a;清除浮动 给需要清除浮动的元素添加类名 clearfix 即可.clearfix::after {content: ;display: block;height: 0;line-height: 0;clear: both;visibility: hidden; }.clearfix {zoom: 1; } 2. 伪元素&#xff1a;实心小三角 .box::after {content: ;displa…
阅读更多...
51单片机开始要学汇编吗

51单片机开始要学汇编吗

那就要看它的编译器的效率了 汇编和C各有千秋 都不可能有人拿他做OS ||| 汇编是要懂一些 但如果你能够都比较通的话就更好了 可以最大限度的利用单片机那可怜的存储空间 &#xff08;再说平台移植是指的在相同硬件结构下不同操作系统间的 编程最好用汇编 C所谓的平台移植性在某…
阅读更多...
java volatile与锁 个人理解

java volatile与锁 个人理解

书上意思: 当把变量声明为volatile类型后&#xff0c;编译器与运行时都会注意到这个变量是共享的&#xff0c;因此不会将该变量上的操作与其他内存操作一起重排序&#xff0c;volatile变量不会被缓存在寄存器或者对其他处理器不可见的地方&#xff0c;因此在读取volatile类型的…
阅读更多...
【Linux 运维】linux系统关机、重启、注销命令

【Linux 运维】linux系统关机、重启、注销命令

linux 关机、重启、注销命令&#xff1a; 关机命令&#xff1a; shutdown -h now 立刻关机&#xff08;生产常用&#xff09;shutdown -h 1 一分钟后关机 ( shutdown -c 可以将刚刚shutdown设置的指令取消取消)halt 立即停止系统&#xff0c;需要人工关闭电源&…
阅读更多...
最新文章

Copyright @ 2022~2023