前言：
第三场比前面两场难度下降了很多，打起来还算比较舒服，这场理论上来说应该可以开7题了，但是场上只写了5题，有两题是思路但是需要再仔细考虑一下的，没开出来有点可惜。
D
思路：
签到题，范围挺小的，没多想，直接一发暴力。
代码：
#include<bits/stdc++.h>
using namespace std;
const int maxn = 2e5 + 10;
typedef long long int ll;
int cal(int x){
int res = 0;
while(x){
res += x % 10;
x /= 10;
}
return res;
}
void solved(){
int n;cin >> n;
int s = cal(n);
for(int i = n + 1; 1 ;i++){
if(cal(i) == s){
cout << i << endl;return ;
}
}
}
int main(){
solved();
return 0;
}
思路：
这题挺简单的，不知道为啥大家都被卡了，因为朋友直接需要相同的糖果，就说明朋友的朋友也是自己的朋友，那么我们只需要建一个图，然后dfs，每次dfs出一个联通块，找出里面的人数和朋友的最大需要的糖果数，把他们相乘然后加起来就行了。
代码：
#include<bits/stdc++.h>
using namespace std;
const int maxn = 2e6 + 10;
typedef long long int ll;
vector<int>G[maxn];
int a[maxn];
bool vis[maxn];
void dfs(int u,int &cnt,int &mm){
vis[u] = true;
mm = max(mm,a[u]);
cnt += 1;
for(int i = 0; i < G[u].size(); i++){
int v = G[u][i];
if(!vis[v]){
dfs(v,cnt,mm);
}
}
}
void solved(){
int n,m;scanf("%d%d",&n,&m);
for(int i = 1; i <= n; i++)scanf("%d",&a[i]);
for(int i = 1; i <= m; i++){
int u,v;scanf("%d%d",&u,&v);
G[u].push_back(v);G[v].push_back(u);
}
ll ans = 0;
for(int i = 1; i <= n; i++){
if(!vis[i]){
int cnt = 0,mm = 0;
dfs(i,cnt,mm);
ans += mm * cnt;
}
}
cout << ans << endl;
}
int main(){
solved();
return 0;
}I
思路：
很显然的一个dp，dp[i]:长度为i的从[1,i]的序列中，子序列的最大美观度。
那么我们面临的决策只有两个，那么当前字符与前面i个字符没有一个相同的即无法增加美观度，那么就是前面i个字符中有与当前i字符相同的这个时候可以增加1美丽度，在这两个决策中取max就行了。
dp[i] = max(dp[i - 1],dp[last[a[i]]] + 1)
代码：
#include<bits/stdc++.h>
using namespace std;
const int maxn = 2e6 + 10;
typedef long long int ll;
int a[maxn];
int dp[maxn];
void solved(){
int n;cin >> n;
for(int i = 1; i <= n; i++)cin >> a[i];
map<int,int>mp;
dp[1] = 0;dp[2] = (a[1] == a[2]);
mp[a[1]] = 1;
mp[a[2]] = 2;
for(int i = 3; i <= n; i++){
if(mp.count(a[i]))
dp[i] = max(dp[i - 1],dp[mp[a[i]]] + 1);
else dp[i] = dp[i - 1];
mp[a[i]] = i;
}
cout << dp[n] << endl;
}
int main(){
solved();
return 0;
}J
思路：
这是一个博弈题，emmmm，通过观察我们可以发现局面其实对牛妹更加有利，因为牛妹要的是偶数，那么如果最后场上有两张牌，即有三种可能，[奇数，偶数]，[偶数，偶数]，[奇数，奇数],那么奇数偶数
偶数，偶数
偶数
偶数，奇数
奇数
偶数。也就是说只要场上只剩下两张牌，不管这些牌是什么，只要这个回合是牛妹的，牛妹必胜。
然后我们可以发现，如果最后场上只有两张牌，并且是牛牛的回合，奇数偶数
奇数，奇数
奇数
奇数，偶数和偶数的永远是偶数，也就是说牛牛只有场上全是偶数才必败，否则必胜，然后我们可以发现如果场上的偶数牌数量<=1,牛牛必胜，否则牛牛必败(牛妹总有办法把局面变得都是偶数和牛牛)。
然后考虑一下n=1,2这题就做完了。
代码：
#include<bits/stdc++.h>
using namespace std;
const int maxn = 2e6 + 10;
typedef long long int ll;
int a[maxn];
void solved(){
int n;cin >> n;
for(int i = 1; i <= n; i++)cin >> a[i];
if(n == 1){
if(a[1] & 1)cout << "NiuNiu" << endl;
else cout << "NiuMei" << endl;
return ;
}
if(n == 2){
if((a[1] % 2 == 1 && a[2] % 2 == 1) || (a[1] % 2 == 1 && a[2] % 2 == 0) || (a[1] % 2 == 0 && a[2] % 2 == 1))
cout << "NiuNiu" << endl;
else cout << "NiuMei" << endl;
}
if(n & 1)cout << "NiuMei" << endl;//牛妹必胜
else {
int f = 0;
for(int i = 1; i <= n; i++){
if(a[i] % 2 == 0)f++;
}
if(f <= 1)cout << "NiuNiu" << endl;
else cout << "NiuMei" << endl;
}
}
int main(){
solved();
return 0;
}H
思路：
这题不难，就是细节比较多，他们的数字相同且字符串不同只有两种方法，要么把转为十进制的>10的且不为10的一个字符拆成两个字符输出，要么把两个字符组合成这个字符输出，要么不存在方案。
代码：
#include<bits/stdc++.h>
using namespace std;
const int maxn = 2e6 + 10;
typedef long long int ll;
char s[maxn];
void solved(){
scanf("%s",s + 1);
int len = strlen(s + 1);
string ans;
string res;
for(int i = 1; i <= len; i++){
int val = s[i] - 'a' + 1;
if(val > 10 && val != 20){
int l = val / 10;
int r = val % 10;
ans += (char)(l + 'a' - 1);
ans += (char)(r + 'a' - 1);
cout << ans;
for(++i;i <= len; i++)cout << s[i];
return ;
}else ans += s[i];
if(val < 10)res += char(val + '0');
else {
res += char((val / 10) + '0');
res += char((val % 10) + '0');
}
}
//cout << res << endl;
string s;
for(int i = 0; i < res.size() - 1; i++){
if(i + 2 < res.size() && res[i + 2] == '0')continue;
if(i + 1 < res.size() && res[i] == '1' && res[i + 1] == '0'){
s += "j";
++i;
continue;
}
if(i + 1 < res.size() && res[i] == '2' && res[i + 1] == '0'){
s += "t";
++i;
continue;
}
int val = (res[i] - '0') * 10 + (res[i + 1] - '0');
if(val > 10 && val <= 26){
s += (char)(val + 'a' - 1);
for(i = i + 2; i < res.size(); i++){
if(res[i] == '1' && res[i + 1] == '0')s += "j",++i;
else if(res[i] == '2' && res[i + 1] == '0')s += "t",++i;
else s += ((res[i] - '0') + 'a' - 1);
}
cout << s << endl;
return ;
}
else {
s += ((res[i] - '0') + 'a' - 1);
}
}
cout << "-1" << endl;
}
int main(){
solved();
return 0;
}C
思路：
数据范围很小，直接暴力dfs，枚举k次攻击，每次攻击选择圆心在[-7,7]，然后计算一下圆内切，外切，相交的数量即可。
代码：
#include<bits/stdc++.h>
using namespace std;
const int maxn = 2e5 + 10;
typedef long long int ll;
struct circle{
int x,y,r;
}c[maxn];
int n,k,r;
int ans = 0;
int px[maxn],py[maxn];
void dfs(int dep){
if(dep >= k){
int res = 0;
for(int i = 1; i <= n; i++){
for(int j = 1; j <= dep; j++){
int dis = (px[j] - c[i].x) * (px[j] - c[i].x) + (py[j] - c[i].y) * (py[j] - c[i].y);
if(dis <= 1ll * (r + c[i].r) * (r + c[i].r) || dis == (r - c[i].r) * (r - c[i].r)){
res ++;break;
}
}
}
ans = max(ans,res);
return ;
}
for(int x = -7; x <= 7; x++){
for(int y = -7; y <= 7; y++){
px[dep + 1] = x;py[dep + 1] = y;
dfs(dep + 1);
}
}
}
void solved(){
cin >> n >> k >> r;
for(int i = 1; i <= n; i++){
scanf("%d%d%d",&c[i].x,&c[i].y,&c[i].r);
}
dfs(0);
cout << ans << endl;
}
int main(){
solved();
return 0;
}F
思路：
emmm，通过不断的wa和观察可以发现，只需要所以串的第一个#之前的字符串相同，和最后一个#的字符串相同即可，就输出-1，否则0.
代码：
#include<bits/stdc++.h>
using namespace std;
const int maxn = 2e6 + 10;
typedef long long int ll;
bool check(string a,string b){
int n = a.size(),m = b.size();
for(int i = 0; i < min(n,m); i++){
if(a[i] == '#' || b[i] == '#')break;
if(a[i] != b[i])return true;
}
for(int i = n - 1,j = m - 1; i && j ; i--,j--){
if(a[i] == '#' || b[j] == '#')break;
if(a[i] != b[j])return true;
}
return false;
}
void solved(){
int n;cin >> n;
string a,b;
bool f = true;
for(int i = 1; i <= n; i++){
if(i == 1){
cin >> a;continue;
}else{
b = a;cin >> a;
}
if(f && check(a,b)){
f = false;
}
}
if(f)cout << "-1" << endl;
else cout << "0" << endl;
}
int main(){
solved();
return 0;
}E
思路：
其实看这个题能***不离十的猜到，应该是用线段树来做，但是可能需要对题目对一定的转换才行。
所以，我们换一个角度思考，给定一个区间[l,r]，如果这个区间的每个数的最近的第一个相同的数<=r就行，否则就不行。于是想暴力肯定是不行，那么我们可以用线段树维护每个数的下一个与这个数相同值的位置，那么可以用next[i]来表示，只需要从后往前for一遍，就可以求出来了，如果没有的话next[i]=n+1,然后用线段树维护这个next数组，那么考虑删除某个数，那么这个数的上一个位置会受到影响，因为上一个数的next就是当前这个数，当前这个数不在了，那么上一个数的next应该是当前这个数的next，那么我们还需要用一个数字来维护上一个数的位置，当发生修改时。
next[x] = n + 1
last[x] = 0
next[last[x]]=next[x]
last[next[x]]=last[x]
代码：
#include<bits/stdc++.h>
using namespace std;
const int maxn = 6e5 + 10;
typedef long long int ll;
int Next[maxn],last[maxn];
int a[maxn];
#define mid (l + r) / 2
#define lson (rt * 2)
#define rson (rt * 2 + 1)
int m[maxn << 2];
int tot;
void build(int l,int r,int rt){
if(l == r){m[rt] = Next[++tot];return ;}
build(l,mid,lson);
build(mid + 1,r,rson);
m[rt] = min(m[lson],m[rson]);
}
void update(int l,int r,int pos,int v,int rt){
if(l == r){m[rt] = v;return ;}
if(pos <= mid)update(l,mid,pos,v,lson);
else update(mid + 1,r,pos,v,rson);
m[rt] = min(m[lson],m[rson]);
}
int query(int l,int r,int ql,int qr,int rt){
if(l >= ql && r <= qr){return m[rt];}
int ans = 1e9;
if(ql <= mid)ans = min(ans,query(l,mid,ql,qr,lson));
if(qr > mid)ans = min(ans,query(mid + 1,r,ql,qr,rson));
return ans;
}
void solved(){
int n,q;cin >> n >> q;
for(int i = 1; i <= n; i++)cin >> a[i],Next[i] = n + 1,last[i] = 0;
map<int,int>mp;
for(int i = 1; i <= n; i++){
if(mp.count(a[i]))
last[i] = mp[a[i]];
mp[a[i]] = i;
}
mp.clear();
for(int i = n; i >= 1; i--){
if(mp.count(a[i]))
Next[i] = mp[a[i]];
mp[a[i]] = i;
}
//for(int i = 1; i <= n; i++)cout << Next[i] << ' ';cout << endl;
build(1,n,1);
while(q--){
int ins;scanf("%d",&ins);
if(ins == 1){
int x;scanf("%d",&x);
if(last[x] != 0)
update(1,n,last[x],Next[x],1);
update(1,n,x,n + 1,1);
Next[last[x]] = Next[x];
last[Next[x]] = last[x];
Next[x] = n + 1;
last[x] = 0;
}else{
int l,r;scanf("%d%d",&l,&r);
printf("%d\n",query(1,n,l,r,1) <= r);
}
}
}
int main(){
solved();
return 0;
}
京公网安备 11010502036488号