蓝桥杯2017年B组C++国赛
admin
|
|
252
|
杂项

1354 字
|
24 分钟

瓷砖样式

题目描述：

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

思路：

暴力枚举+check+去重

只能竖着放和横着放，所以就对每个点去枚举横着放和竖着放

所有点都放完了就check一下，看看是不是符合题意的那个

然后再进行字符串处理，扔进set中去重

下面是两种dfs的代码，第一个是根据num直接获得此时的x和y，而第二个是去跑循环判断哪个点没走过，来获得x和y

总的来说这两个代码在本地都跑了差不多三秒，我以为扔上去会TLE，没想到卡着900ms过了(>_<)

不愧是暴力杯，这测评姬完全是为暴力而存在的啊 orzzzzzz

#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;
//不开longlong见祖宗！
inline int IntRead(){char ch = getchar();int s = 0, w = 1;while(ch < '0' || ch > '9'){if(ch == '-') w = -1;ch = getchar();}while(ch >= '0' && ch <= '9'){s = s * 10 + ch - '0';ch = getchar();}return s * w;}
inline ll llRead(){ll x(0), t(1);char o (getchar());while (o < '0' || o > '9') {if (o == '-') {t = -1;}o = getchar();}for (; o >= '0' && o <= '9'; o = getchar()) {x = (x << 1) + (x << 3) + (o ^ 48);}return x * t;}

int n, m;
int ans;
int vis[5][20];

bool check(){
    for(int i = 0; i < n - 1; ++i){
        for(int j = 0; j < m - 1; ++j){
            int a = vis[i][j] + vis[i + 1][j] + vis[i][j + 1] + vis[i + 1][j + 1];
            if(a == 4 || a == 8)return false;
        }
    }
    return true;
}


set<string>se;

void dfs(int num){
    if(num == n * m){
        if(check()){
            ++ans;
            string s = "";
            for(int i = 0; i < n; ++i){
                for(int j = 0; j < m; ++ j){
                    s += '0' + vis[i][j];
                }
            }
//            cout<<s<<endl;
            se.insert(s);
        }
        return;
    }
    int x = num / m;
    int y = num % m;
    if(vis[x][y] != 0)dfs(num + 1);
    else {
        if(x + 1 < n &&vis[x + 1][y] == 0){
            vis[x][y] = vis[x + 1][y] = 1;
            dfs(num + 1);
            vis[x][y] = vis[x + 1][y] = 2;
            dfs(num + 1);
            vis[x][y] = vis[x + 1][y] = 0;
        }
        if(y + 1 < m && vis[x][y + 1] == 0){
            vis[x][y] = vis[x][y + 1] = 1;
            dfs(num + 1);
            vis[x][y] = vis[x][y + 1] = 2;
            dfs(num + 1);
            vis[x][y] = vis[x][y + 1] = 0;
        }
    }
    
}


int main(){
//    cin>>n>>m;
    n = 3;m = 10;
    dfs(0);
//    cout<<ans<<endl;
    cout<<se.size()<<endl;
    return 0;
}


#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;
//不开longlong见祖宗！
//inline __int128 read(){__int128 x = 0, f = 1;char ch = getchar();while(ch < '0' || ch > '9'){if(ch == '-'){f = -1;}ch = getchar();}while(ch >= '0' && ch <= '9'){x = x * 10 + ch - '0';ch = getchar();}return x * f;}
//inline void print(__int128 x){if(x < 0){putchar('-');x = -x;}if(x > 9){print(x / 10);}putchar(x % 10 + '0');}
inline ll llRead(){ll x(0), t(1);char o (getchar());while (o < '0' || o > '9') {if (o == '-') {t = -1;}o = getchar();}for (; o >= '0' && o <= '9'; o = getchar()) {x = (x << 1) + (x << 3) + (o ^ 48);}return x * t;}
inline int IntRead(){char ch = getchar();int s = 0, w = 1;while(ch < '0' || ch > '9'){if(ch == '-') w = -1;ch = getchar();}while(ch >= '0' && ch <= '9'){s = s * 10 + ch - '0';ch = getchar();}return s * w;}
inline void write(int x){if (x < 0) {x = ~x + 1; putchar('-');}if (x > 9){write(x / 10);}putchar(x % 10 + '0');}
ll qpow(ll a,ll n){ll ans=1,base=a%mod;while(n){if(n&1)ans=(ans*base)%mod;base=(base*base)%mod;n>>=1;}return ans;}
inline ll gcd(ll x, ll y) { return y ? gcd(y, x % y) : x; }

int n, m;
int vis[5][20];
int ans;

bool judge(){
    for(int x = 1; x <= n - 1; ++x){
        for(int y = 1; y <= m - 1; ++y){
            int p = vis[x][y] + vis[x + 1][y] + vis[x][y + 1] + vis[x + 1][y + 1];
                    if(p == 4 || p == 8)return false;
        }
    }
    return true;
}

string s;
set<string>se;

void dfs(int num){
    if(num == n * m){
        if(judge()){
            s = "";
            for(int i = 1; i <= n; ++i){
                for(int j = 1; j <= m; ++j){
                    s += '0' + vis[i][j];
                }
            }
            se.insert(s);
        }
        
        return;
    }
    for(int x = 1; x <= n; ++x){
        for(int y = 1; y <= m; ++y){
            if(vis[x][y] == 0){
                if(x + 1 <= n && vis[x + 1][y] == 0){
                    vis[x][y] = vis[x + 1][y] = 2;
                    dfs(num + 2);
                    vis[x][y] = vis[x + 1][y] = 1;
                    dfs(num + 2);
                    vis[x][y] = vis[x + 1][y] = 0;
                }
                if(y + 1 <= m && vis[x][y + 1] == 0){
                    vis[x][y] = vis[x][y + 1] = 2;
                    dfs(num + 2);
                    vis[x][y] = vis[x][y + 1] = 1;
                    dfs(num + 2);
                    vis[x][y] = vis[x][y + 1] = 0;
                }
                return;
            }
        }
    }
    return;
}

int main(){
    n = 3;m = 10;

    dfs(0);
    cout<<se.size()<<endl;
    return 0;
}

发现杯

题目描述：

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

思路：

是拓扑排序的题

首先熟悉一下拓扑排序判环的时候，是记录有多少点进入了queue，也就记录了入度为0的点，拿这个数和总共的点数去比较

这道题，是一颗树，这个树上有一个环，让你升序输出环上的点

因为这个树是无向树，所以我们把入度和出度放在一起当作节点的度，所以拓扑排序后环上的点的度会等于2，利用这个特点，我们就拓扑排序一遍，再循环找一遍谁的度等于2即可

这里给出邻接矩阵和链式前向星的写法

写链式前向星的时候，数组要double一下，还有建边要建双向……，wa了一晚上呢

#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;
//不开longlong见祖宗！

int n, x, y;
vector<int>tr[MAX];
int in[MAX];
queue<int>q;

void topu(){
    while (!q.empty()) {
        int now = q.front();
        q.pop();
        for(int i = 0; i < tr[now].size(); ++i){
            --in[tr[now][i]];
            if(in[tr[now][i]] == 1)q.push(tr[now][i]);
            
        }
    }
}

int main(){
    cin>>n;
    for(int i = 1; i <= n; ++i){
        x = IntRead();
        y = IntRead();
        ++in[x];
        ++in[y];
        tr[x].push_back(y);
        tr[y].push_back(x);
    }
    for(int i = 1; i <= n; ++i){
        if(in[i] == 1)q.push(i);
    }
    topu();
    for(int i = 1; i <= n; ++i){
        if(in[i] == 2)cout<<i<<' ';
    }
    cout<<endl;
    
    return 0;
}

#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 200000 + 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;
//不开longlong见祖宗！

int n, tot;
int x, y;
int head[MAX];
bool vis[MAX];
int in[MAX];
struct ran{
    int to, next;
}tr[MAX];
queue<int>q;

void built(int u, int v){
    tr[++tot].next = head[u];
    tr[tot].to = v;
    head[u] = tot;
}

void topu(){
    while (!q.empty()) {
        int now = q.front();q.pop();
//        if(vis[now])continue;
//        vis[now] = 1;
        for(int i = head[now]; i != -1; i = tr[i].next){
            --in[tr[i].to];
            if(in[tr[i].to] == 1)q.push(tr[i].to);
        }
    }
}



int main(){
    n = IntRead();
    mem(tr, -1);
    mem(head, -1);
    for(int i = 1; i <= n; ++i){
        x = IntRead();y = IntRead();
        built(x, y);
        built(y, x);
        ++in[x];
        ++in[y];
    }
    for(int i = 1; i <= n; ++i){
        if(in[i] == 1)q.push(i);
    }
    topu();
    for(int i = 1; i <= n; ++i){
        if(in[i] > 1)cout<<i<<' ';
    }
    cout<<endl;
    return 0;
}

对局匹配

题目描述：

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

思路：

dp题

如果 k = 0，那么只用考虑总过出现了多少不同积分的用户数，因为相同积分的用户只能上线一个。

如果 k > 0，假设当前用户积分为 x，则他能影响到的用户积分为 x + k 和 x – k，又会因为积分为 x + k 用户在线与否间接地影响到 x + 2k……可以发现积分对 k 求余相同的用户可能会互相影响。因此我们可以根据每个用户积分对 k 求余的结果分成余数为 0 ~ k – 1 的组，共 k 组。此时我们只要解决每一组的最多在线人数最后求和即可。对于这类枚举选取方案求最值的问题，很容易想到用动态规划剪枝。

设计动态规划状态：dp[i] 表示，在当前分组内，积分从 0 到 i 的范围内最多有多少用户可以同时上线。num[i] 代表积分为 i 的用户有多少个。(因为所有的数字都会被分到确定的一组里，所以我们可以共用一个 dp 数组来同时处理 k 组的答案。)

那么对于 dp[i]，只有两种方法转移而来：

1.积分为 i 的用户上线，所以积分为 i – k 的用户不能上线，但是对积分为 i - 2 * k 及以下的没有影响，dp[i] = num[i] + dp[i - 2 * k];

2.积分为 i 的用户没有上线，所以积分为 i – k 的用户可以上线，直接等于积分为 i – k 及以下的答案即可，dp[i] = dp[i- k];

转移方程： dp[i] = max(dp[i - 2 * k] + num[i], dp[i - k]);

事实上 num 数组可以直接初始化到 dp 数组中，并将转移方程改为 dp[i] = max(dp[i - 2 * k] + dp[i], dp[i - k]);

初始化：dp[0~1e5] = 每个数字出现的个数；

#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 200000 + 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;
//不开longlong见祖宗！
inline int IntRead(){char ch = getchar();int s = 0, w = 1;while(ch < '0' || ch > '9'){if(ch == '-') w = -1;ch = getchar();}while(ch >= '0' && ch <= '9'){s = s * 10 + ch - '0';ch = getchar();}return s * w;}
inline ll llRead(){ll x(0), t(1);char o (getchar());while (o < '0' || o > '9') {if (o == '-') {t = -1;}o = getchar();}for (; o >= '0' && o <= '9'; o = getchar()) {x = (x << 1) + (x << 3) + (o ^ 48);}return x * t;}

int n, k;
vector<int>v;
int x;
int dp[MAX];
int vis[MAX];
int xu[MAX];
int ans;

int main(){
    cin>>n>>k;
    for(int i = 1; i <= n; ++i){
        cin>>x;
        if(dp[x] == 0){
            ++ans;
        }
        ++dp[x];
    }
    if(!k)cout<<ans<<endl;
    else{
        ans = 0;
        for(int i = 1; i < MAX; ++i){
            if(i >= 2 * k)dp[i] = max(dp[i] + dp[i - 2 * k], dp[i - k]);
            else dp[i]  = max(dp[i], dp[i - k]);
        }
        for(int i = MAX - 1; i >= MAX - k; --i)ans += dp[i];
        cout<<ans<<endl;
    }
    return 0;
}

 

博客内容均系原创，未经允许严禁转载！
蓝桥杯
暂无评论

发送评论 编辑评论 


				

			

						

				

					

						

							

								
							

							
						

					

				

				

					

						

							

								
							

							
						

					

				

				

					

						

							

								
							

							
							
													

					

				

			

			
			

				

					
				

			

				

											

							
							
						

																					

							
							
						

										
					
											
						

	

		
|´・ω・)ノ
ヾ(≧∇≦*)ゝ
(☆ω☆)
（╯‵□′）╯︵┴─┴
￣﹃￣
(/ω＼)
∠( ᐛ 」∠)＿
(๑•̀ㅁ•́ฅ)
→_→
୧(๑•̀⌄•́๑)૭
٩(ˊᗜˋ*)و
(ノ°ο°)ノ
(´இ皿இ｀)
⌇●﹏●⌇
(ฅ´ω`ฅ)
(╯°A°)╯︵○○○
φ(￣∇￣o)
ヾ(´･ ･｀｡)ノ"
( ง ᵒ̌皿ᵒ̌)ง⁼³₌₃
(ó﹏ò｡)
Σ(っ °Д °;)っ
( ,,´･ω･)ﾉ"(´っω･｀｡)
╮(╯▽╰)╭
o(*////▽////*)q
＞﹏＜
( ๑´•ω•) "(ㆆᴗㆆ)
😂
😀
😅
😊
🙂
🙃
😌
😍
😘
😜
😝
😏
😒
🙄
😳
😡
😔
😫
😱
😭
💩
👻
🙌
🖕
👍
👫
👬
👭
🌚
🌝
🙈
💊
😶
🙏
🍦
🍉
😣
Source: github.com/k4yt3x/flowerhd
	

	

		
颜文字
Emoji
小恐龙
花!
	


									

			

			
			
		

	






上一篇
下一篇 

                    

                    
			        推荐文章
		            

		            

							
第十二届蓝桥杯省赛第一场C++A组 「左孩子右兄弟」

							
							

							
第十二届蓝桥杯省赛第一场C++「砝码称重」

							
							

							
蓝桥杯2019 年B组C++国赛

							
							

							
第十一届蓝桥杯省赛第一场C++A/B组真题题解

							
							

							
蓝桥杯2018年C++组国赛