蓝桥杯2018年C++组国赛

换零钞

题目描述：

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-jPBJ6nGf-1622213898945)(/Users/chelsea/Library/Application Support/typora-user-images/image-20210528210410825.png)]

思路：

设1元有x张，5元有y张，则2元有10x张

直接写出线性方程：

$21x + 5y = 200$

眼瞅都能看出来只有x等于5的时候有整数解，带入就可以得到

如果眼瞅不出来，那就写扩展欧几里得求解

不会扩欧的点这里

#include<map>
#include<set>
#include<list>
#include<deque>
#include<stack>
#include<queue>
#include<cmath>
#include<bitset>
#include<cstdio>
#include<string>
#include<vector>
#include<sstream>
#include<cstring>
#include<limits.h>
#include<stdlib.h>
#include<iostream>
#include<algorithm>
using namespace std;
#define endl '\n'
#define inf 0x3f3f3f3f
#define MAX 100000 + 50
#define seed 13331
#define mod 1000000007
#define io ios::sync_with_stdio(false); cin.tie(0); cout.tie(0)
#define mem(a,b) memset((a),(b),sizeof(a))
typedef  long long ll ;

int x, y, gcd, a, b, c;

void exgcd(int a, int b, int &gcd, int &x, int &y){
    if(b == 0){
        gcd = a;
        y = 0;
        x = 1;
    }
    else {
        exgcd(b, a % b, gcd, y, x);
            y -= x * (a / b);
    }
}

int main(){
    cin>>a>>b>>c;
    exgcd(a, b, gcd, x, y);
    x *= c / gcd;
    y *= c / gcd;
    while (x < 0 || y < 0) {
        x -= b / gcd;
        y += a / gcd;
    }
    cout<<11 * x + y<<endl;
    return 0;
}

激光样式

题目描述：

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-Hh2Sfofm-1622213898947)(/Users/chelsea/Library/Application Support/typora-user-images/image-20210528212638064.png)]

思路1：二进制枚举

因为只有30个灯，再加上是填空题，就完全可以用二进制去模拟

模拟从0到(1<<30) – 1的数，然后写个check函数判断符合题意否

#include<map>
#include<set>
#include<list>
#include<deque>
#include<stack>
#include<queue>
#include<cmath>
#include<bitset>
#include<cstdio>
#include<string>
#include<vector>
#include<sstream>
#include<cstring>
#include<limits.h>
#include<stdlib.h>
#include<iostream>
#include<algorithm>
using namespace std;
#define endl '\n'
#define inf 0x3f3f3f3f
#define MAX 10000 + 50
#define seed 13331
#define mod 1000000007
#define io ios::sync_with_stdio(false); cin.tie(0); cout.tie(0)
#define mem(a,b) memset((a),(b),sizeof(a))
typedef  long long ll ;

bool now, pre;
int ans, n;

bool check(int x){
    pre = x & 1;
    x >>= 1;
    while (x) {
        now = x & 1;
        if(now == 1 && pre == 1)return false;
        pre = now;
        x >>= 1;
    }
    return true;
}

int main(){
    
    n = 30;
    for(int i = 0; i <= (1 << n) - 1; ++i){
        if(check(i))++ans;
    }
    cout<<ans<<endl;
    return 0;
}

思路2: DFS

dfs的时候就判断一下上一个灯是开还是没开，如果开了本次的点就不开，如果没开，那本次的点开或不开都可以

还要记得扔进set中去重

注意结束条件是num == n + 1

#include<map>
#include<set>
#include<list>
#include<deque>
#include<stack>
#include<queue>
#include<cmath>
#include<bitset>
#include<cstdio>
#include<string>
#include<vector>
#include<sstream>
#include<cstring>
#include<limits.h>
#include<stdlib.h>
#include<iostream>
#include<algorithm>
using namespace std;
#define endl '\n'
#define inf 0x3f3f3f3f
#define MAX 10000 + 50
#define seed 13331
#define mod 1000000007
#define io ios::sync_with_stdio(false); cin.tie(0); cout.tie(0)
#define mem(a,b) memset((a),(b),sizeof(a))
typedef  long long ll ;
typedef unsigned long long ull;

int n;
int ans;
bool vis[100];
set<string>se;
string s;

void dfs(int x){
    if(x == n + 1){
        s = "";
        for(int i = 1; i <= n; ++i)s += '0' + vis[i];
        se.insert(s);
        return;
    }
    if(vis[x - 1] == 1){
        vis[x] = 0;
        dfs(x + 1);
    }
    else if(vis[x - 1] == 0){
        dfs(x + 1);
        vis[x] = 1;
        dfs(x + 1);
        vis[x] = 0;
    }
    return;
}

int main(){
    n = 30;
    dfs(0);
    cout<<se.size()<<endl;
    return 0;
}

调手表

题目描述：

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-XXCDYvwY-1622213898947)(/Users/chelsea/Library/Application Support/typora-user-images/image-20210528213134866.png)]

思路1: DP

对于每个时间点，最晚的调回时间其实就是它本身，也就是从0开始一个一个的按加一的按钮

而对于k * x % n的结果，是可以通过只按k来优化，当然不一定非得通过k，也可能用1更好，或者1和k同时用更好

对于这个题有两种按法，我们可以先解决一种按法，在此基础上再利用另一种按法去优化次数

也就是，我们就可以先循环从1到n跑一遍，这一遍就是都按k，就可以更新余数的最小次数，再跑一遍， $dp[i] = min(dp[i], dp[i - 1] + 1)$

#include<map>
#include<set>
#include<list>
#include<deque>
#include<stack>
#include<queue>
#include<cmath>
#include<bitset>
#include<cstdio>
#include<string>
#include<vector>
#include<sstream>
#include<cstring>
#include<limits.h>
#include<stdlib.h>
#include<iostream>
#include<algorithm>
using namespace std;
#define endl '\n'
#define inf 0x3f3f3f3f
#define MAX 100000 + 50
#define seed 13331
#define mod 1000000007
#define io ios::sync_with_stdio(false); cin.tie(0); cout.tie(0)
#define mem(a,b) memset((a),(b),sizeof(a))
typedef  long long ll ;
typedef unsigned long long ull;

int n, k;
int dp[MAX];

int main(){
    cin>>n>>k;
    for(int i = 1; i <= n; ++i)dp[i] = i;
    int cnt = 0;
    for(int i = 1; i < n; ++i){
        cnt = (cnt + k) % n;
        dp[cnt] = min(dp[cnt], i);
    }
  	for(int i = 1; i < n; ++i){
    dp[i] = min(dp[i - 1] + 1, dp[i]);
  	}
    int maxn = 0;
    for(int i = 0; i < n; ++i){
        maxn = max(maxn, dp[i]);
    }
    cout<<maxn<<endl;
    return 0;
}

思路2: 最短路BFS

通过观察可以发现，问题其实就是0到n-1的点到0的距离！！！

每个相邻的点的距离是1

对于结点 x，到结点 (x+1)%n 和结点 (x+k)%n 之间存在一条权值为 1 的有向边。

这就可以用最短路来做

再加上本题的权值都为1，就可以转成BFS来做

这样就和直接VJ的抓牛的题有点相似叻

#include<map>
#include<set>
#include<list>
#include<deque>
#include<stack>
#include<queue>
#include<cmath>
#include<bitset>
#include<cstdio>
#include<string>
#include<vector>
#include<sstream>
#include<cstring>
#include<limits.h>
#include<stdlib.h>
#include<iostream>
#include<algorithm>
using namespace std;
#define endl '\n'
#define inf 0x3f3f3f3f
#define MAX 100000 + 50
#define seed 13331
#define mod 1000000007
#define io ios::sync_with_stdio(false); cin.tie(0); cout.tie(0)
#define mem(a,b) memset((a),(b),sizeof(a))
typedef  long long ll ;

int n, k, now, nextt;
int vis[MAX];
int dis[MAX];
queue<int>q;

void bfs(){
    q.push(0);
    vis[0] = 1;
    while (!q.empty()) {
        now = q.front();q.pop();
        nextt = now + 1;//第一种走法：走1
        nextt %= n;
        if(vis[nextt] == 0){
            dis[nextt] = dis[now] + 1;
            vis[nextt] = 1;
            q.push(nextt);
        }
        nextt = now + k;//第二种走法：走k
        nextt %= n;
        if(vis[nextt] == 0){
            dis[nextt] = dis[now] + 1;
            vis[nextt] = 1;
            q.push(nextt);
        }
    }
}


int main(){
    cin>>n>>k;
    bfs();
    int maxn = 0;
    for(int i = 0; i < n; ++i)maxn = max(maxn, dis[i]);
    cout<<maxn<<endl;
    return 0;
}

搭积木

题目描述：

思路：

记忆化搜索！

因为规则1的约束，所以上面的只能在下面的基础上建造，所以要由下往上去递归

当判断到第h层[l, r]的区间内时，如果没问题，就去递归h + 1层的[l, r]区间

用个记忆化，不然会TLE

递归变量就是层数 h，区间左右端点l, r

check函数就是去判读h层，l到r的区间内有没有空隙

#include<map>
#include<set>
#include<list>
#include<deque>
#include<stack>
#include<queue>
#include<cmath>
#include<bitset>
#include<cstdio>
#include<string>
#include<vector>
#include<sstream>
#include<cstring>
#include<limits.h>
#include<stdlib.h>
#include<iostream>
#include<algorithm>
using namespace std;
#define endl '\n'
#define inf 0x3f3f3f3f
#define MAX 100000 + 50
#define seed 13331
#define mod 1000000007
#define io ios::sync_with_stdio(false); cin.tie(0); cout.tie(0)
#define mem(a,b) memset((a),(b),sizeof(a))
typedef  long long ll ;

ll n, m;
ll dp[105][105][105];
char tr[105][105];

bool check(int h, int l, int r){
    for(int i = l; i <= r; ++i){
        if(tr[h][i] == 'X')return false;
    }
    return true;
}

ll cal(int h, int l, int r){
    if(h > n || !check(h, l, r))return 0;
    ll ans = 1;
    for(int L = l; L <= r; ++L){
        for(int R = L; R <= r; ++R){
            if(dp[h + 1][L][R] != -1)ans += dp[h + 1][L][R];
            else ans += cal(h + 1, L, R);
            ans %= mod;
        }
    }
    dp[h][l][r] = ans;
    return ans;
}

int main(){
    cin>>n>>m;
    mem(dp, -1);
    for(ll i = n; i >= 1; --i)scanf(" %s", tr[i] + 1);
    ll cnt = 1;
    for(int i = 1; i <= m; ++i){
        for(int j = i; j <= m; ++j){
            cnt += cal(1, i, j);
            cnt %= mod;
        }
    }
    cout<<cnt<<endl;
    return 0;
}

换零钞

题目描述：

思路：

激光样式

题目描述：

思路1：二进制枚举

思路2: DFS

调手表

题目描述：

思路1: DP

思路2: 最短路BFS

搭积木

题目描述：

思路：

发送评论 编辑评论

推荐文章

发送评论编辑评论