2024牛客寒假集训营第二场

标签：typedef const int long 2024 牛客 pair 集训营 define

总的来说，这一场还是很不错的，但是还是有做的不好的地方，比方说靠别人给了D的思路，还有思维的太慢。不过继续努力吧！
A.Tokitsukaze and Bracelet

思路：签到题，直接按着题目的意思模拟就可以了。
code：

点击查看代码

#include<bits/stdc++.h>                      
using namespace std;
#define fi first
#define se second
#define lc p<<1
#define rc p<<1|1
//#define int long long
#define vi vector<int>
#define vpi vector<pair<int,int>>
#define vvi vector<vector<int>>
typedef long long ll;
typedef pair<int,int> PII;
typedef pair<ll,pair<ll,ll>> PIII;
typedef pair<ll,pair<ll,pair<ll,ll>>> pIIII;
const int N = 2e5 + 7;
const int inf = 0x3f3f3f3f;
const int mod = 998244353;
void solve() {
    int a,b,c;cin >> a >> b >> c;
    int sum = 0;
    if(a == 150) sum += 1;
    else if(a == 200) sum += 2;
    if(b == 34 || b == 36 || b == 38 || b == 40) sum += 1;
    else if(b == 45) sum += 2;
    if(c == 34 || c == 36 || c == 38 || c == 40) sum += 1;
    else if(c == 45) sum += 2;
    cout << sum << "\n";
}
signed main() {	
	std::ios::sync_with_stdio(0);
	std::cin.tie(0);
	int t = 1;
	cin >> t;
	while(t--) {
		solve();
	}
    //system("pause");
	return 0;
}
/*
Do smth instead of nothing and stay organized
Don't get stuck on one approach
*/

B.Tokitsukaze and Cats

思路：我们可以发现，如果有两只猫互相相邻(一只在另外一只的上、下、左、右)，那么两只猫之前用的隔板数量就会减1，然后由于a和b相邻的那么b和a也是相邻的，所以记得除2。
code：

点击查看代码

#include<bits/stdc++.h>                      
using namespace std;
#define fi first
#define se second
#define lc p<<1
#define rc p<<1|1
//#define int long long
#define vi vector<int>
#define vpi vector<pair<int,int>>
#define vvi vector<vector<int>>
typedef long long ll;
typedef pair<int,int> PII;
typedef pair<ll,pair<ll,ll>> PIII;
typedef pair<ll,pair<ll,pair<ll,ll>>> pIIII;
const int N = 2e5 + 7;
const int inf = 0x3f3f3f3f;
const int mod = 998244353;
int dir[5][5] = {{-1,0},{1,0},{0,1},{0,-1}};
int n,m;
bool inmap(int x,int y) {
    return (x >= 1 && x <= n && y >= 1 && y <= m);
}
void solve() {
    int k;
    cin >> n >> m >> k;
    vvi st(n + 1,vi(m + 1));
    vi x(n + 1),y(m + 1);
    for(int i = 1; i <= k; i++) {
        cin >> x[i] >> y[i];
        st[x[i]][y[i]] = 1;
    }
    int cnt = 0;
    for(int i = 1; i <= k; i++) {
        for(int j = 0; j < 4; j++) {
            int dx = x[i] + dir[j][0];
            int dy = y[i] + dir[j][1];
            if(inmap(dx,dy)) 
                if(st[dx][dy]) cnt++;
        }
    }
    //cout << cnt << "\n";
    cout << k*4 - cnt/2 << "\n";
}
signed main() {	
	std::ios::sync_with_stdio(0);
	std::cin.tie(0);
	int t = 1;
	//cin >> t;
	while(t--) {
		solve();
	}
    //system("pause");
	return 0;
}
/*
Do smth instead of nothing and stay organized
Don't get stuck on one approach
*/

C.Tokitsukaze and Min-Max XOR
c暂时还不会，感觉是字典树什么的，补了再来写。
D.Tokitsukaze and Slash Draw

思路分析：
这题是个最短路问题，因为考虑到n在5000以内，m在1000以内，所以总共就n张牌。所以我们可以考虑对于每个点去考虑用每个技能牌能够到达哪个位置。由于是从当前位置往“上”走，所以对于可以到达的点建一个单向边就可以了。所以我们考虑从牌堆底部到牌堆顶部的牌的编号是n到1，那么我们要求的就是从k号点走到n号点。所以直接Dijkstra就可以了，实现起来不是很复杂。我这题是在太过极限了，2分钟写完，然后一直找不到哪里错了，直道想到自己数组可能没有清空才改对，对的时候还有两秒结束比赛。汗流浃背。
code

点击查看代码

#include<bits/stdc++.h>                      
using namespace std;
#define fi first
#define se second
#define lc p<<1
#define rc p<<1|1
#define int long long
#define vi vector<long long>
#define vpi vector<pair<long long,long long>>
#define vvi vector<vector<int>>
typedef long long ll;
typedef pair<long long,long long> PII;
typedef pair<ll,pair<ll,ll>> PIII;
typedef pair<ll,pair<ll,pair<ll,ll>>> pIIII;
const int N = 7000 + 7;
const long long inf = 1e18;
const int mod = 998244353;
vpi g[N];
vi dis(N),vis(N);
int n,m,k;
void Dijkstra(int s) {
	priority_queue<PII,vector<PII>,greater<PII>> q;
	for(int i = 1; i <= N - 1; i++) dis[i] = inf;
	dis[k] = 0;
	q.push({0,k});
	while(!q.empty()) {
		auto t = q.top();q.pop();
		if(vis[t.second]) continue;
		vis[t.second] = 1;	
		for(auto i : g[t.second]) {
			if(dis[i.fi] > dis[t.second] + i.se) {
				dis[i.fi] = dis[t.second] + i.se;
				q.push({dis[i.fi],i.fi});
			}
		}
	}
}
void solve() {
    cin >> n >> m >> k;
    vi a(N),b(N);
    for(int i = 1; i <= N - 1; i++) {
        g[i].clear();
    }
    for(int i = 1; i <= m; i++) {
        cin >> a[i] >> b[i];
        for(int j = 1; j <= n; j++) {
            int v = (j + a[i] - 1)%n + 1;
            g[j].push_back({v,b[i]});
        }
    }
    fill(vis.begin(),vis.end(),0);
    Dijkstra(k);
    if(dis[n] == 1e18 || dis[n] < 0) cout << "-1\n";
    else cout << dis[n] << "\n";
}
signed main() {	
	std::ios::sync_with_stdio(0);
	std::cin.tie(0);
	int t = 1;
	cin >> t;
	while(t--) {
		solve();
	}
    //system("pause");
	return 0;
}
/*
Do smth instead of nothing and stay organized
Don't get stuck on one approach
*/

E.Tokitsukaze and Eliminate (easy)

思路分析：这是我第一个AC的题目，没想到居然A，B才是签到题。我第一个看这个题是因为这个题目比较短hhh。所以对于这个题，由于不同的数字最多就两个，所以可以直接暴力从右到左寻找每个集齐这几个不同的元素的区间，然后直接删掉就好了。如果没找到，那么肯定只能一个一个删掉，所以说这个策略一定是最优的。
code:

点击查看代码

#include<bits/stdc++.h>                      
using namespace std;
#define fi first
#define se second
#define lc p<<1
#define rc p<<1|1
//#define int long long
#define vi vector<int>
#define vpi vector<pair<int,int>>
#define vvi vector<vector<int>>
typedef long long ll;
typedef pair<int,int> PII;
typedef pair<ll,pair<ll,ll>> PIII;
typedef pair<ll,pair<ll,pair<ll,ll>>> pIIII;
const int N = 2e5 + 7;
const int inf = 0x3f3f3f3f;
const int mod = 998244353;
void solve() {
    int n;cin >> n;
	vi a(n + 1);
	int dif = 0;
	set<int> s;
	for(int i = 1; i <= n; i++) {
		cin >> a[i];
		s.insert(a[i]);
	}
	dif = s.size();
	set<int> st;
	int cnt = 0,last,res = 0;
	for(int i = n; i >= 1; i--) {
		st.insert(a[i]);
		res++;
		if(st.size() == dif) {
			res = 0;
			cnt++,st.clear();
			last = i;
		}
	}
	cnt += res;
	cout << cnt << "\n";
}
signed main() {	
	std::ios::sync_with_stdio(0);
	std::cin.tie(0);
	int t = 1;
	cin >> t;
	while(t--) {
		solve();
	}
    //system("pause");
	return 0;
}
/*
Do smth instead of nothing and stay organized
Don't get stuck on one approach
*/

F.Tokitsukaze and Eliminate (hard)

思路分析：这里我们可以发现，不同的数字已经变得更多了，所以上一题的贪心不一定还适用，因为我们可以考虑一下这个样例：1 2 1 2 3，就会发现正确的应该是2，但是由上一题的思路我跑出来的是3。所以要换一个新的思路！

标签：typedef,const,int,long,2024,牛客,pair,集训营,define
From： https://www.cnblogs.com/Jerry114514/p/18008918

2024牛客寒假集训营第二场

相关文章

赞助商

阅读排行