第一周训练个人题解

318 阅读 0 评论 0 点赞

####  Day.1
#####  问题 2083：十进制转十六进制
  解题思路：进制转换裸体，用除留余数法模拟即可

```cpp
#include <iostream>
#include <cstdio>
#include <cstring>
#include <vector>
#include <algorithm>
using namespace std;
typedef long long ll;
typedef pair<int,int> P;
const int inf=0x3f3f3f3f;
const int maxn=1e3+7;
char a[17]={'0','1','2','3','4','5','6','7','8','9','A','B','C','D','E','F'};
int n,m,t;
vector<int> v;
int main()
{
    scanf("%d",&n);
    if(n==0){
        puts("0");
        return 0;
    }
    v.clear();
    while(n){
        v.push_back(n%16);
        n/=16;
    }
    reverse(v.begin(),v.end());
    for(int i=0;i<(int)v.size();i++){
        if(v[i]<=9)printf("%d",v[i]);
        else printf("%c",a[v[i]]);
    }
    printf("\n");
    return 0;
}
```
#####  问题 2086：最长公共子序列
解题思路：经典dp，设原串s,t，设dp[i][j]为s串前i个和$t$串前j个字母的最长公共子序列。

状态转移方程为: 
 dp[i][j]=dp[i-1][j-1]+1(s[i]==s[j])
 
 dp[i][j]=max(dp[i-1][j],dp[i][j-1])(s[i]!=s[j])
 
 由于dp[i][j]第一层只与“i-1”或“i”有关(由递推方程可知)，所以可以优化空间，利用01滚动节省空间。
```cpp
#include <iostream>
#include <cstdio>
#include <cstring>
#include <vector>
#include <algorithm>
using namespace std;
typedef long long ll;
typedef pair<int,int> P;
const int inf=0x3f3f3f3f;
const int maxn=1e3+7;

int n;
int dp[2][maxn];
char s[maxn],t[maxn];
int main()
{
    cin>>s>>t;
    int len1=strlen(s),len2=strlen(t);
    for(int i=0;i<len1;i++){
        for(int j=0;j<len2;j++){
            if(s[i]==t[j]){
                dp[(i+1)%2][j+1]=dp[(i)%2][j]+1;
            }
            else {
                dp[(i+1)%2][j+1]=max(dp[(i)%2][j+1],dp[(i+1)%2][j]);
            }
        }
    }
    cout<<dp[len1%2][len2]<<'\n';
    return 0;
}
```
#####  问题 2088：快速幂
解题思路：快速幂裸体，利用了分治的思想，大大减少乘的次数，从而保证了时间复杂度。
```cpp
#include <iostream>
#include <cstdio>
#include <cstring>
#include <vector>
#include <algorithm>
using namespace std;
typedef long long ll;
typedef pair<int,int> P;
const int inf=0x3f3f3f3f;
const int maxn=1e3+7;

ll a,b,mod;
ll qpow(ll x,ll n){
    ll ret=1;
    x%=mod;//x可能很大，要先模操作，防止乘爆
    while(n>0){
        if(n&1)ret=(ret*x)%mod;
        x=(x*x)%mod;
        n/=2;
    }
    return ret;
}
int main()
{
    cin>>a>>b>>mod;
    cout<<qpow(a,b)<<'\n';
    return 0;
}
```
####  Day.2
#####  问题 1115：DNA
 解题思路：找规律控制格式输出空格和X即可，本人用递归代替循环执行。

```cpp
#include <iostream>
#include <cstdio>
#include <cstring>
#include <vector>
#include <algorithm>
using namespace std;
typedef long long ll;
typedef pair<ll,int> P;
const ll inf=1e12+7;
const int maxn=1e5+7;
#define ft first
#define sd second
#define pb push_back
int n;
void solve(int a,int b){
    for(int i=1;i<=a/2+1;i++){//输出一个的上半段(包括中心X)
        for(int j=1;j<i;j++)printf(" ");
        printf("X");
        if(i==a/2+1){
            printf("\n");break;
        }
        for(int j=1;j<=a-2*i;j++)printf(" ");
        printf("X\n");
    }
    for(int i=1;i<a/2;i++){//输出后半段，不包括最后一行
        for(int j=i;j<a/2;j++)printf(" ");
        printf("X");
        for(int j=1;j<=2*i-1;j++)printf(" ");
        printf("X\n");
    }
    if(b==1){//最后再输出最后一行
        printf("X");
        for(int i=1;i<=a-2;i++)printf(" ");
        printf("X\n");
    }
    else solve(a,b-1);//递归
}
int main()
{
    scanf("%d",&n);
    while(n--){
        int a,b;scanf("%d%d",&a,&b);
        solve(a,b);
        printf("\n");
    }
    return 0;
}
```
#####  问题 1434：回文数字
  解题思路：范围较小，从小到大暴力查找每个数是或不是即可。

```cpp
#include <iostream>
#include <cstdio>
#include <cstring>
#include <vector>
#include <algorithm>
using namespace std;
typedef long long ll;
typedef pair<ll,int> P;
const ll inf=1e12+7;
const int maxn=1e5+7;
#define ft first
#define sd second
#define pb push_back
int n;
int flag=0;
bool judge(int x){
    int sum=0,now=0,yy=x,xx;
    if(x<100000)xx=10000;
    else xx=100000;
    while(x){
        int l=x%10;
        now+=l*xx;
        xx/=10;
        sum+=l;
        x/=10;
    }
    if(sum==n&&now==yy)return true;
    return false;
}
int main()
{
    scanf("%d",&n);
    for(int i=10001;i<=999999;i++){
        if(judge(i)){
            flag=1;
            printf("%d\n",i);
        }
    }
    if(!flag)puts("-1");
    return 0;
}
```
#####  问题 2194：递增三元组
 解题思路：由于n很大，所以不能暴力找，所以需要改变想法，对于 A 数组中，我们需要知道每个数 a[i] 在 B 中有多少个数大于它，对于 B 中的每个数 b[i] ，也是一样，去 C 里找有多少个数大于它。所以可以先对三个数组从小到大排序，然后二分预处理出这些需要找的数的个数于数组中，设前后这两个数组分别为 d[],e[] 。然后我们对 e 数组求一个前缀和数组     g[] ，对于A中的每个数 a[i] ，它有几个三元组满足题意，将其存入 ans[i] 中，根据前面我们所求信息，很容易想到：ans[i]=(g[n-1]-g[n-d[i]-1]) 也就是后缀数组 g[] 的一个后缀。因为我们排过序，满足题意的数一定是后缀。最后求和即可。

```cpp
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
#include <cmath>
using namespace std;
typedef long long ll;
const int maxn=2e6+7;
bool isp[maxn];
int pri[maxn],cnt;
ll ans[maxn];
int n;
void init(){
    int N=2e6;
    isp[0]=isp[1]=1;
    for(int i=2;i<=N;i++){
        if(!isp[i])pri[cnt++]=i;
        for(int j=0;j<cnt&&i*pri[j]<=N;j++){
            isp[i*pri[j]]=1;
            if(i%pri[j]==0)break;
        }
    }
    for(int i=1;i<=N;i++){
        if(!isp[i])ans[i]=ans[i-1]+i;
        else ans[i]=ans[i-1];
    }
}
int main(){
    init();
    scanf("%d",&n);
    printf("%lld\n",ans[n]);
    return 0;
}
```
#####  问题 1913：排列数
 解题思路：经典的搜索题，递归原理不熟，试着拿别人代码调试一下，理解递归过程。
```cpp
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
#include <cmath>
using namespace std;
typedef long long ll;
const int maxn=2e6+7;
int a[20];
bool vis[maxn];
int n,no;
void dfs(int s){
    if(no>=n)return;
    if(s==10){
        no++;
        if(no==n){
            for(int i=0;i<10;i++)printf("%d",a[i]);
            printf("\n");
            return;
        }
    }
    for(int i=0;i<10;i++){
        if(!vis[i]){
            vis[i]=1;
            a[s]=i;
            dfs(s+1);
            vis[i]=0;//回溯状态要还原
        }
    }
}
int main(){
    scanf("%d",&n);
    dfs(0);
    return 0;
}
```
#####  问题 1923：学霸的迷宫
 解题思路：经典搜索题，求迷宫最短路径问题一般用bfs求解，路径记录可以在结构体里记录，也可以用二维数组记录。本人习惯用二维数组记录前驱，dfs回溯输出路径。要求字典序最小，遍历顺序需要为:DLRU

```cpp
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>
#include <cmath>
using namespace std;
typedef long long ll;
typedef pair<int,int> P;
const int maxn=1e3+7;
bool vis[maxn][maxn];
int n,m;
char a[maxn][maxn];
int dx[4]={1,0,0,-1},dy[4]={0,-1,1,0};//DLRU
int path[maxn][maxn];//记录前驱
int ss[maxn][maxn];//记录到当前点的最短步数
char str[4]={'U','R','L','D'};
void dfs(int s,int x,int y){//回溯输出路径
    if(x==0&&y==0)return;
    if(s==0)dfs(path[x+1][y],x+1,y);
    else if(s==1)dfs(path[x][y-1],x,y-1);
    else if(s==2)dfs(path[x][y+1],x,y+1);
    else if(s==3)dfs(path[x-1][y],x-1,y);
    printf("%c",str[s]);
}
void bfs(){
    queue<P> q;
    q.push(P(0,0));
    vis[0][0]=1;
    ss[0][0]=0;
    while(!q.empty()){
        P p=q.front();q.pop();
        if(p.first==n-1&&p.second==m-1){
            break;
        }
        for(int i=0;i<4;i++){
            int nx=p.first+dx[i],ny=p.second+dy[i];
            if(nx>=0&&nx<n&&ny>=0&&ny<m&&!vis[nx][ny]&&a[nx][ny]=='0'){
                vis[nx][ny]=1;
                q.push(P(nx,ny));
                if(i==0)path[nx][ny]=3;
                else if(i==1)path[nx][ny]=2;
                else if(i==2)path[nx][ny]=1;
                else if(i==3)path[nx][ny]=0;
                ss[nx][ny]=ss[p.first][p.second]+1;
            }
        }
    }
    printf("%d\n",ss[n-1][m-1]);
    dfs(path[n-1][m-1],n-1,m-1);
    printf("\n");
}
int main(){
    scanf("%d%d",&n,&m);
    for(int i=0;i<n;i++){
        cin>>a[i];
    }
    bfs();
    return 0;
}
```
####  Day.4
#####  问题 1427：买不到的数目
  解题思路：数学规律题

```cpp
#include<iostream>
using namespace std;
int main()
{
    int a,b;
    while(cin>>a>>b)cout<<(a*b-a-b)<<endl;
    return 0;
}
```
#####  问题 1565：质数的后代
  解题思路：质因子分解后判断一下所分解的质数的个数即其幂次是否满足题意即可。

```cpp
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>
#include <cmath>
using namespace std;
typedef long long ll;
typedef pair<int,int> P;
const int inf=0x3f3f3f3f;
const int maxn=1e3+7;
const int mod=123456789;
#define pb push_back
#define ft first
#define sd second
int t,n,m;
priority_queue<int> pq;
int main()
{
    while(!pq.empty())pq.pop();
    while(~scanf("%d",&n)){
        if(n==0)break;
        pq.push(n);
    }
    pq.pop();
    cout<<pq.top()<<'\n';
    return 0;
}
```
####  Day.5
#####  问题 1102：明明的随机数
  解题思路：set,map具有去重，自动排序的特性，时间复杂度是O(logn)，所以可以用set解决。
  
```cpp
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <set>
#include <cmath>
using namespace std;
typedef long long ll;
typedef pair<int,int> P;
const int inf=0x3f3f3f3f;
const int maxn=1e3+7;
const int mod=123456789;
#define pb push_back
#define ft first
#define sd second
int t,n,m;
set<int> s;
set<int>::iterator it;
int main()
{
    s.clear();
    scanf("%d",&n);
    for(int i=0;i<n;i++){
        scanf("%d",&m);
        s.insert(m);
    }
    cout<<s.size()<<endl;
    for(it=s.begin();it!=s.end();it++){
        if(it==s.begin())printf("%d",(*it));
        else printf(" %d",(*it));
    }
    printf("\n");
    return 0;
}
```
#####  问题 1431：分糖果
 解题思路：模拟下即可，需要用辅助数组记录下每次，每个人糖果的一半是多少。本人用map，判断每轮所有人的糖果是否相等。
```cpp
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <map>
#include <cmath>
using namespace std;
typedef long long ll;
typedef pair<int,int> P;
const int inf=0x3f3f3f3f;
const int maxn=1e2+7;
const int mod=123456789;
#define pb push_back
#define ft first
#define sd second
int t,n;
map<int,int> m;
int a[maxn],b[maxn];
int main()
{
    scanf("%d",&n);
    int ans=0;
    m.clear();
    for(int i=0;i<n;i++){
        scanf("%d",&a[i]);
        b[i]=a[i]/2;
        m[a[i]]++;
    }
    while(m.size()!=1){
        m.clear();
        for(int i=0;i<n;i++){
            a[i]+=b[(i+1)%n];
        }
        for(int i=0;i<n;i++){
            a[i]-=b[i];
        }
        for(int i=0;i<n;i++){
            if(a[i]%2==1){
                a[i]++;ans++;
            }
            b[i]=a[i]/2;
            m[a[i]]++;
        }
    }
    cout<<ans<<'\n';
    return 0;
}
```
#####  问题 1873：合根植物
解题思路：并查集裸体，维护下共根的点在一个集合里，最后统计下并查集中维护的集合即可。

```cpp
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <map>
#include <cmath>
using namespace std;
typedef long long ll;
typedef pair<int,int> P;
const int inf=0x3f3f3f3f;
const int maxn=1e6+7;
const int mod=123456789;
#define pb push_back
#define ft first
#define sd second
int k,n,m;
int p[maxn],ans[maxn];
int fin(int x){
    return x==p[x]?x:p[x]=fin(p[x]);
}
void unite(int x,int y){
    x=fin(x),y=fin(y);
    if(x!=y)p[x]=y;
}
bool same(int x,int y){
    return fin(x)==fin(y);
}
int main()
{
    scanf("%d%d",&m,&n);
    int len=n*m;
    for(int i=1;i<=len;i++)p[i]=i;
    scanf("%d",&k);
    while(k--){
        int x,y;scanf("%d%d",&x,&y);
        if(!same(x,y))unite(x,y);
    }
    for(int i=1;i<=len;i++){
        ans[fin(i)]++;
    }
    int sum=0;
    for(int i=1;i<=len;i++){
        if(ans[i])sum++;//统计集合个数
    }
    cout<<sum<<endl;
    return 0;
}
```
####  Day.6
#####  问题 1255：能量项链
 解题思路：区间dp模板题，首先将环拆成链，定义$dp[i][j]$为从第$i$颗珠子到第$j$颗珠子聚合的最大能量。
 不难推出状态转移方程：
 $dp[i][j]=max(dp[i][k]+dp[k+1][j]+a[i]*a[k+1]*a[j+1])(i<=k<j)$
可以把一段聚合后的珠子看作一个珠子，状态转移方程就容易理解了。
```cpp
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
#include <cmath>
using namespace std;
const int maxn=2e2+7;

int n;
int a[maxn];
int dp[maxn][maxn];
int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;i++){
        scanf("%d",a+i);
        a[i+n]=a[i];
    }
    for(int j=1;j<=(n<<1);j++){
        for(int i=j-1;i>=1;i--){
            for(int k=i;k<j;k++){
                dp[i][j]=max(dp[i][j],a[i]*a[k+1]*a[j+1]+dp[i][k]+dp[k+1][j]);
            }
        }
    }
    int ans=0;
    for(int i=1;i<=n;i++){
        ans=max(ans,dp[i][i+n-1]);
    }
    cout<<ans<<'\n';
    return 0;
}
```
#####  问题 1464：分解质因数
解题思路：按顺序对每个数进行质因子分解即可，控制好输出格式即可。

```cpp
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
#include <cmath>
using namespace std;
typedef long long ll;
typedef pair<int,int> P;
const int inf=0x3f3f3f3f;
const int maxn=1e3+7;
const int mod=123456789;
#define pb push_back
#define ft first
#define sd second
int t,n,m;
vector<P> v;//first存素数，second存指数
void getp(int x){//对x进行质因子分解
    v.clear();
    for(int i=2;i*i<=x;i++){
        v.pb(P(i,0));
        while(x%i==0)x/=i,++v.back().sd;
        if(!v.back().sd)v.pop_back();
    }
    if(x>1)v.pb(P(x,1));
}
int main()
{
    int l,r;
    scanf("%d%d",&l,&r);
    for(int i=l;i<=r;i++){
        getp(i);
        printf("%d=",i);
        int flag=0;
        for(int j=0;j<(int)v.size();j++){
            if(v[j].sd==1){
                if(!flag){
                    flag=1;
                    printf("%d",v[j].ft);
                }
                else printf("*%d",v[j].ft);
            }
            else {
                for(int k=1;k<=v[j].sd;k++){
                    if(!flag){
                        flag=1;
                        printf("%d",v[j].ft);
                    }
                    else printf("*%d",v[j].ft);
                }
            }
        }
        puts("");
    }
    return 0;
}
```
#####  问题 1474：阶乘计算
解题思路：大数乘法模拟即可。

```cpp
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
#include <cmath>
using namespace std;
typedef long long ll;
typedef pair<int,int> P;
const int inf=0x3f3f3f3f;
const int maxn=1e3+7;
const int mod=123456789;
const ll m=1e8;
#define pb push_back
#define ft first
#define sd second
int t,n;
struct Bigint{
	ll s[1000];int l;//l为长度
	void print(){
		printf("%lld",s[l]);
		for(int i=l-1;i>=0;i--)printf("%08lld",s[i]);
	}
	void read(ll x){//将整数x存入高精度数组
		l=-1;memset(s,0,sizeof(s));
		do{
			s[++l]=x%m;
			x/=m;
		}while(x);
	}
}ans;
Bigint operator * (int b,Bigint a){//int与大数乘(顺序不能换)
	ll d=0;
	for(int i=0;i<=a.l;i++){
		d+=a.s[i]*b;a.s[i]=d%m;
		d/=m;
	}
	while(d){
		a.s[++a.l]=d%m;
		d/=m;
	}
	return a;
}
int main()
{
    scanf("%d",&n);
    ans.read(1);
    for(int i=2;i<=n;i++){
        ans=i*ans;
    }
    ans.print();
    return 0;
}
```
####  Day.7
#####  问题 1548：盾神与砝码称重
 解题思路：如果把物体放在天平右盘，可以爆搜将每个砝码依次试着放左盘，放右盘或者不放，直到左右盘重量相等为止，都放过也不行就说明没有可行方案。

```cpp
#include <iostream>
#include <cstdio>
#include <stack>
#include <unordered_set>
using namespace std;
typedef long long ll;
typedef pair<int,int> P;
const int inf=0x3f3f3f3f;
const int maxn=1e3+7;
const int N=1e6+10;
#define pb push_back
#define ft first
#define sd second
int n,m,ans,ma;
int a[30];
bool dfs(int l,int r,int s){
    if(l==r)return true;//左右盘重量相等
    if(s>=n)return false;//都试过也不行
    if(dfs(l,r,s+1))return true;//这个砝码两边都不放
    if(dfs(l+a[s],r,s+1)||dfs(l,r+a[s],s+1))return true;//放左边或右边
    return false;
}
int main()
{
    scanf("%d%d",&n,&m);
    for(int i=0;i<n;i++){
        scanf("%d",&a[i]);
    }
    for(int i=0;i<m;i++){
        int x;scanf("%d",&x);
        if(dfs(0,x,0))puts("YES");
        else puts("NO");
    }
    return 0;
}
```
#####  问题 1630：摆动序列
解题思路：爆搜即可，一有合法方案，就加到答案中。

```cpp
#include <iostream>
#include <cstdio>
#include <stack>
using namespace std;
typedef long long ll;
typedef pair<int,int> P;
const int inf=0x3f3f3f3f;
const int maxn=1e3+7;
const int N=1e6+10;
#define pb push_back
#define ft first
#define sd second
int n,m,ans;
int dp[30];
int a[30];
bool vis[30];
bool judge(int v,int x){//判断v加入后是否合法
    if(x<=1)return true;
    if((a[x-2]<a[x-1]&&v<a[x-2])||(a[x-1]<a[x-2]&&v>a[x-2]))return true;
    return false;
}
void dfs(int s){
    if(s>n)return;
    if(s==n){
        return;
    }
    for(int i=1;i<=n;i++){
        if(!vis[i]&&judge(i,s)){
            a[s]=i;
            if(s>=1)ans++;//有可行方案ans就++
            vis[i]=1;
            dfs(s+1);
            vis[i]=0;
        }
    }
}
int main()
{
    scanf("%d",&n);
    dfs(0);
    cout<<ans<<'\n';
    return 0;
}
```

0.0分

0 人评分

本文分类：文章列表
浏览次数：318 次浏览
发布日期：2020-01-16 16:18:23
本文链接：https://blog.dotcpp.com/a/64717

上一篇 > Day1~Day3训练总结
下一篇 > 计日器的switch-case语句实现

C语言网提供由在职研发工程师或ACM蓝桥杯竞赛优秀选手录制的视频教程，并配有习题和答疑，点击了解：

一点编程也不会写的：零基础C语言学练课程

解决困扰你多年的C语言疑难杂症特性的C语言进阶课程

从零到写出一个爬虫的Python编程课程

只会语法写不出代码？手把手带你写100个编程真题的编程百练课程

信息学奥赛或C++选手的必学C++课程

蓝桥杯ACM、信息学奥赛的必学课程：算法竞赛课入门课程

手把手讲解近五年真题的蓝桥杯辅导课程

第一周训练个人题解

评论列表共有 0 条评论

发表评论取消回复

第一周训练个人题解

数位dp#2491: 信息学奥赛一本通T1587-Windy 数(C++)

点进来你会后悔的

简简单单的循环

简单的回文数

评论列表 共有 0 条评论

发表评论 取消回复

评论列表共有 0 条评论

发表评论取消回复