Day1
SMU Winter 2023 Round #5 (Div.2)
A. Lucky?
1.字符转数字
2.相加并比较
#include<bits/stdc++.h>
using namespace std;
string s;
int a[10];
int main()
{
int t;
cin>>t;
int sum1,sum2;
while(t--){
cin>>s;
sum1=0,sum2=0;
for(int i=0;i<6;i++){
a[i]=s[i]-'0';
}
for(int i=0;i<3;i++){
sum1+=a[i];
}
for(int i=3;i<6;i++){
sum2+=a[i];
}
if(sum1==sum2){
printf("YES\n");
}
else{
printf("NO\n");
}
}
return 0;
}
B.Equal Candies
1.找最小值
2.每个分别相减求和
#include<bits/stdc++.h>
using namespace std;
int main(void) {
int n;
cin >> n;
int m;
int a[1005];
for (int i = 0; i < n; i++) {
cin >> m;
int minv = 1e8;//赋一个极大值
int sum = 0;
for (int j = 0; j < m; j++) {
cin >> a[j];
minv = min(minv, a[j]);//找最哪个盒子里糖果最少
}
for (int j = 0; j < m; j++) {
sum += a[j] - minv;//每一个盒子里的糖果减最少的就是要吃的
}
cout << sum << endl;
}
}
C.Most Similar Words
1.找最相似的数的意思是找相减的数最小的
2.直接挨个相减
#include<bits/stdc++.h>
using namespace std;
int main()
{
int t, n, m, i, j, x;
int min, sum;
char C[51][9];
cin>>t;
while (t--) {//t组case
cin>>n>>m;
min = 300;
for (i = 0; i<n; i++) scanf("%s", C[i]);//要比较的字符串，n个串串
for (i = 0; i<n; i++) //每个字符串都互相比较一下
{
for (j = i + 1; j<n; j++)
{
sum = 0;
for (x = 0; x<m; x++)//每个字符串的每个字母互相比较
{
if (C[i][x]>C[j][x])
{
sum = sum + (C[i][x] - C[j][x]);
}
else
{
sum = sum + (C[j][x] - C[i][x]);
}
}
if (sum<min) //找最小的
{
min = sum;
}
}
}
printf("%d\n", min);//输出最小的
}
return 0;
}
D.X-Sum
#include<bits/stdc++.h>
using namespace std;
const int N = 210;
typedef long long LL;
int w[N][N];
int T,n,m;
LL get(int x,int y)//x的攻击范围相加
{
int res=w[x][y];
for(int i=1;i<=200;i++)
{
if(x-i>=1&&y-i>=1) res+=w[x-i][y-i];//左上角“\”
if(x+i<=n&&y+i<=m) res+=w[x+i][y+i];//右上角“/”
if(x+i<=n&&y-i>=1) res+=w[x+i][y-i];//左下角“/”
if(x-i>=1&&y+i<=m) res+=w[x-i][y+i];//右下角“\”
}
return res;
}
int main()
{
scanf("%d", &T);
while(T--)
{
scanf("%d%d", &n, &m);
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
{
scanf("%d", &w[i][j]);//存图
}
LL res=0;
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
{
res=max(res,get(i,j));//棋盘上每个点都遍历一遍，找x的攻击范围最大的
}
printf("%lld\n",res);
}
return 0;
}
E.Eating Queries
1.对于每次询问，回答最少要吃多少糖果>=询问的数目
2.如果全加起来都不大于cout<<-1
思路：排序，一种糖果只能吃一次，因此依次遍历直到所有糖果都没有
#include<bits/stdc++.h>
using namespace std;
int main()
{
int T;cin>>T;
while(T--)
{
int n,q;cin>>n>>q;
vector<int> a(n);
for(int i=0;i<n;i++) cin>>a[i];
sort(a.begin(),a.end(),greater<int>());//从大到小排序
for(int i=1;i<n;i++) a[i]+=a[i-1];//前缀和，吃i种糖果的糖分，我们约定a[0]=0；
for(int i=0;i<q;i++)
{
int x;
cin>>x;
if(x>a[n-1])//x大于所有糖果加起来
cout<<"-1"<<endl;
else
{
int pos=lower_bound(a.begin(),a.end(),x)-a.begin();//找到大于等于pos的最小下标
cout<<pos+1<<endl;//从0开始记得+1
}
}
}
return 0;
}
F. Longest Strike
1.给定一个数组，要求找到连续的区间[l,r]使得区间长度最大
2.区间内的数满足>=k
#include<bits/stdc++.h>
using namespace std;
const int N = 3 * 1e5 + 100;
int T;
int n, m;
int a[N], s[N], num[N];
bool cmp(long long aa, long long b) {
return aa > b;
}
int main() {
cin >> T;
while (T--) {
scanf("%d%d", &n, &m);
for (int i = 1; i <= n; i++) {
scanf("%d", &a[i]);
}
sort(a + 1, a + 1 + n);
int idx = 0;
for (int i = 1; i <= n; i++) {
int j = i;
while (a[j] == a[j + 1] && (j + 1 <= n))j++;
s[++idx] = j - i + 1;
num[idx] = a[i];
i = j;
}
int l = -1, r = -1, len = -1;
for (int i = 1; i <= idx; i++) {
int j = i;
while ((j + 1 <= idx) && s[j] >= m && s[j + 1] >= m && (num[j + 1] == num[j] + 1))j++;
if ((l == -1 || num[j] - num[i] > len) && s[j] >= m) {
l = i, r = j;
len = num[j] - num[i];
}
i = j;
}
if (l != -1) {
printf("%d %d\n", num[l], num[r]);
// cout << num[l] << num[r] << endl;
} else printf("-1\n");
}
return 0;
}
G.White-Black Balanced Subtrees
1.储存树的模板
2.遍历树每个结点的模板
3.dfs遍历所有结点的模板
4.用结构体或者pair来存储两种颜色和有多少棵子树两种颜色相同
#include<bits/stdc++.h>
//树的遍历
using namespace std;
const int N = 2 * 1e4 + 100;
int T;
int n, m;
int e[N], ne[N], h[N], idx;
string s;
int res = 0;
typedef pair<pair<int, int>, int> pii;
void add(int a, int b) // 添加一条边a->b
{
e[idx] = b, ne[idx] = h[a], h[a] = idx++;
}
pii dfs(int x) {
int W = 0, B = 0;
W += s[x - 1] == 'W' ? 1 : 0;//判断这个结点是什么颜色，对应颜色个数加1
B += s[x - 1] == 'B' ? 1 : 0;
for (int i = h[x]; i != -1; i = ne[i]){//遍历每个父子节点的每个结点
int j = e[i];
pii P = dfs(j);//求每一个父节点下的子节点的颜色
W += P.first.first;//相加可得父节点的颜色
B += P.first.second;
}
if (W == B && W != 0) {
res++;
//cout << x << endl;;
}
pii p = {{W, B}, res};//用pii类型存储
return p;
}
int main() {
cin >> T;
while (T--) {
res = 0;
idx = 0;
memset(h, -1, sizeof h);
scanf("%d", &n);//有n个结点
for (int i=2;i<=n;i++) {//求的就是不包含根节点的子树
int x;
scanf("%d",&x);
add(x, i);
}
cin >> s;//每个结点的颜色
dfs(1);//从根节点遍历
printf("%d\n", res);
}
return 0;
}
Day2
闲来无事
ACwing-第k个数(快速选择法排序)
1.快速选择法排序
2.找到第k个数
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10;
int a[N];
int n,k;
int q_sort(int l,int r,int k){
if(l==r) return a[l];//只有一个数
int x=a[l],i=l-1,j=r+1;
while(i<j)
{
while(a[++i]<x);//<a[l]放在左边
while(a[--j]>x);//>a[l]放在右边
if(i<j) swap(a[i],a[j]);//不符合就交换位置
}
int sl= j-l+1;//<a[l]的个数
if(k<=sl) return q_sort(l,j,k);//k在左边,包括j
return q_sort(j+1,r,k-sl);//k在右边,不包括k
}
int main()
{
cin>>n>>k;
for(int i=0;i<n;i++){
cin>>a[i];
}
cout<<q_sort(0,n-1,k)<<endl;//0排到n-1
}
ACwing-逆序对的数量(归并法排序)
1.用归并分别求左,右,中间的逆序对
2.其实都是mid-i+1一直递归求出来的
#include<bits/stdc++.h>
using namespace std;
const int N=1e6;
int n;
long long a[N];
long long tmp[N];//中间数组
long long meger_sort(int l,int r){
if(l>=r) return 0;
int mid=l+r>>1;
//求逆序对
long long res=meger_sort(l,mid)+meger_sort(mid+1,r);
//归并
int k=0,i=l,j=mid+1;
//tmp从0开始
while(i<=mid&&j<=r)//任意一边没有到头
{
if(a[i]<=a[j])//如果右边的大于左边，先将左边放入tmp
{
tmp[k++]=a[i++];
}
else
{
tmp[k++]=a[j++];
res+=mid-i+1;//如果左边的大于右边,逆序了,记录一下
//注意,是以mid为边界,不要干涉到mid+1这边,因为这边也继续递归算出
}
}
//有一边先结束，扫尾
while(i<=mid) tmp[k++]=a[i++];
while(j<=r) tmp[k++]=a[j++];
//物归原主，将tmp的值复制到从l开始的数组中
for(int i=l,j=0;i<=r;i++,j++){
a[i]=tmp[j];
}
return res;
}
int main()
{
cin>>n;
for(int i=0;i<n;i++){
cin>>a[i];
}
cout<<meger_sort(0,n-1)<<endl;//n个数,求到逆序对的个数，并排好序输出
return 0;
}
ACwing-三次方根(浮点数二分)
1.用double
2.浮点数二分不需要考虑边界
#include<bits/stdc++.h>
using namespace std;
double binary(double n)
{
double l=-10000,r=10000;
while(r-l>1e-8){
double mid=(l+r)/2;
if(mid*mid*mid>=n) r=mid;
else l=mid;
}
return l;
}
int main()
{
double n;
scanf("%lf",&n);
printf("%lf",binary(n));
return 0;
}
ACwing-前缀和(一维)
1.从1开始
2.默认0位置为0
#include<bits/stdc++.h>
using namespace std;
const long long N=100005;
long long a[N];
long long s[N];
long long m,n;
int main()
{
scanf("%lld%lld",&n,&m);
for(long long i=1;i<=n;i++) scanf("%lld",&a[i]);
for(long long i=1;i<=n;i++) s[i]=s[i-1]+a[i];
while(m--){
long long l,r;
scanf("%lld%lld",&l,&r);
printf("%lld\n",s[r]-s[l-1]);
}
return 0;
}
ACwing-子矩阵(二维前缀和)
1.二维数组不能开太大
2.记二维前缀和模板
#include<bits/stdc++.h>
using namespace std;
const int N=1e3+10;
int a[N][N];
int s[N][N];
int n,m,q;
int main()
{
scanf("%d%d%d",&n,&m,&q);
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
scanf("%d",&a[i][j]);
//初始化前缀和数组
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
s[i][j]=s[i-1][j]+s[i][j-1]-s[i-1][j-1]+a[i][j];//这条求s[i][j]
}
}
//q次询问
while(q--){
int x1,y1,x2,y2;
scanf("%d%d%d%d",&x1,&y1,&x2,&y2);
printf("%d\n",s[x2][y2]-s[x1-1][y2]-s[x2][y1-1]+s[x1-1][y1-1]);//这条求某个小方形面积
}
return 0;
}
2023寒假牛客算法基础集训营-A World Final? World Cup! (I)
1.给出10次点球的结果
2.有奇数，偶数区分A和B的结果
3.如果A和B比赛进行到某个阶段，后面A全胜（或者后面B全胜）A都无法超过B（B都无法超过A），说明判断出来了。
#include<bits/stdc++.h>
using namespace std;
int main()
{
int t;
cin>>t;
while(t--)
{
string s;
cin>>s;
bool f=false;
int a1=0,b1=0;
int res=0;
for(int i=0;i<10;i++){//从0开始奇数表示B，偶数表示A
if(i%2==0){
if(s[i]=='1'){
a1++;
}
}
else{
if(s[i]=='1'){
b1++;
}
}
res++;//记录这是第几场比赛
if(b1>a1+(10-i-1)/2||a1>b1+(10-i)/2){//奇数偶数不一样
f=true;
break;
}
}
if(f){
cout<<res<<endl;
}
else{
cout<<-1<<endl;
}
}
return 0;
}
ACwing-差分
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10;
int b[N];//差分数组
int a[N];//操作数组
int insert(int l,int r,int c){
b[l]+=c;
b[r+1]-=c;
}
int main()
{
int n,m;
cin>>n>>m;
for(int i=1;i<=n;i++){
cin>>a[i];
insert(i,i,a[i]);//初始时，ab数组为0，a要插入值
}
//询问
while(m--)
{
int l,r,c;
cin>>l>>r>>c;
insert(l,r,c);
}
for(int i=1;i<=n;i++){
a[i]=a[i-1]+b[i];//差分数组b的前缀和等于a
}
for(int i=1;i<=n;i++){
cout<<a[i]<<" ";
}
cout<<endl;
return 0;
}
ACwing-差分矩阵（二维差分）
#include<bits/stdc++.h>
using namespace std;
const int N=1e3+100;
int b[N][N];//差分数组
int a[N][N];//操作数组
void insert(int x1,int y1,int x2,int y2,int c){
b[x1][y1]+=c;
b[x2+1][y1]-=c;
b[x1][y2+1]-=c;
b[x2+1][y2+1]+=c;
}
int main()
{
int n,m,q;
cin>>n>>m>>q;
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
cin>>a[i][j];
insert(i,j,i,j,a[i][j]);
}
}
//询问
while(q--)
{
int x1,y1,x2,y2,c;
cin>>x1>>y1>>x2>>y2>>c;
insert(x1,y1,x2,y2,c);
}
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
a[i][j]=a[i-1][j]+a[i][j-1]-a[i-1][j-1]+b[i][j];
}
}
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
cout<<a[i][j]<<" ";
}
cout<<endl;
}
return 0;
}
Day 3
2023牛客寒假算法基础集训营2
A. Tokitsukaze and a+b=n (easy)
1.给定两个区间，分别在这连个区间内找a,b
2.求a+b=n的种类数
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e5+10;
int main()
{
int t;
cin>>t;
ll n;
cin>>n;
while(t--)
{
ll res=0;
ll l1,r1,l2,r2;
cin>>l1>>r1>>l2>>r2;
for(int i=l1;i<=r1;i++){
if(n-i>=l2&&n-i<=r2){
res++;
}
}
}
return 0;
}
B.Tokitsukaze and a+b=n (medium)
1.这题o(n)也不行，直接tle
2.数学规律，因为两个区间都是公差为1的等差数列
3.他们之间都是找到一个数可以a+b=n，之后就全部对应相加
#include<bits/stdc++.h>
using namespace std;
int t,n,l1,l2,r1,r2;
int main()
{
cin>>t;
while(t--)
{
cin>>n>>l1>>r1>>l2>>r2;
if(l1+l2>n||r1+r2<n){
cout<<0<<endl;
continue;
}
cout<<max(0,min(n-l1,r2)-max(n-r1,l2)+1)<<endl;
}
}
C.Tokitsukaze and a+b=n (hard)
1,本题不再是两个区间，而是m个区间中任选两个
2.本题要求输出%998244353的结果
#include<bits/stdc++.h>
using namespace std;
const int N = 4e5+10;
const int mod = 998244353;
#define int long long
int n,m;
int a[N];
signed main()
{
cin>>n>>m;
int ans =0;
for(int i=1;i<=m;i++)//m次循环找到每次方法
{
int l,r;
cin >> l >> r;
a[l]+=1;
a[r+1]-=1;
ans= (ans-max(min(n-l,r)-n+min(n-l,r)+1, (int)0))%mod;
}
for(int i=1;i<=2e5+10;i++)
a[i] = (a[i-1]+a[i])%mod;
for(int i=0;i<=n;i++)
ans=(ans+a[i]*a[n-i]%mod)%mod;
cout<<ans;
}
D.Tokitsukaze and Energy Tree
1.n个结点的能量数，根节点为1
2.n个能量球，能量树的每个节点都恰好有一个能量球
3.放置能量球在某结点之后，能获得以这个结点为根节点的子树的所有能量、
4.输出最多能获得多少总能量
思路：
1.树要从下往上遍历
2.每个结点被加次数等于深度
3.树形dfs 我还不熟练
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
int n,v[200010],x,h[200010];//v存储能量球的能量，h来记录每个结点的深度
LL ans;//用来记录最大总能量
vector<int>g[200010];
void dfs(int x,int d)
{
h[x] = d;
for (int i = 0;i < g[x].size();i++)
{
dfs(g[x][i],d+1); //若没找到父亲节点就是0，但h从1开始
}
}
int main()
{
scanf("%d",&n); //n个能量球
for (int i = 2;i <= n;i++) //i的父亲节点x,并顺便把每个结点命名为1~n
{
scanf("%d",&x);
g[x].push_back(i);
}
for (int i = 1;i <= n;i++) //能量球的能量
{
scanf("%d",&v[i]);
}
dfs(1,1);
sort(v+1,v+1+n,greater<int>()); //能量升序
sort(h+1,h+1+n,greater<int>()); //根结点升序
LL ans = 0;
for (int i = 1;i <= n;i++)
{
ans += 1ll*h[i]*v[i]; //遍历每个结点
}
cout<<ans<<endl;
return 0;
}
E.Tokitsukaze and Function
1.均值不等式
2.二分，寻找sqrt(n)
#include <bits/stdc++.h>
#define PII pair<int, int>
#define pll pair<long, long>
#define int long long
using namespace std;
const int maxn = 5e5 + 10; // 记得看数组范围是否开够
const int inf = 0x3f3f3f3f;
int n;
int f(int x)
{
return n / x + x - 1;
}
bool check(int x,int num)
{
int ans = f(x);
if(ans>num)
return false;
else
return true;
}
int erfen(int a,int b,int num)
{
while(a<b)
{
int mid = (a + b) / 2;
if(check(mid,num))
{
b = mid;
}
else{
a = mid + 1;
}
}
return a;
}
void solve()
{
int l, r;
cin >> n >> l >> r;
int x = sqrt(n);
int y=x*(2+x);
if(y>n)
{
x--;
}
int ans = 0;
if(l<=x)
{
if(r<=x)
{
int num = f(r);
ans=erfen(l,r,num);
}
else{
int a = f(x);
int b = f(x + 1);
if(a>b)
{
ans = x+1;
}
else{
ans=erfen(l,x,a);
}
}
}
else {
ans = l;
}
cout << ans << endl;
}
signed main()
{
ios::sync_with_stdio(false);
cin.tie(0), cout.tie(0);
int t = 1;
cin >> t;
while (t--)
{
solve();
}
return 0;
}
F/G.Tokitsukaze and Gold Coins (easy/hard)
1.迷宫（n*3）。迷宫起点（1，1），迷宫终点（n,3）每个格子都有一条向下和一条向右的单向道路。
2.在迷宫的起点设有离开迷宫的出口，玩家可以通过出口安全的离开迷宫。
普通的Dfs
#include<bits/stdc++.h>
using namespace std;
const int MAXN = 5e5 + 5;
#define int long long
int n, k;
int mt[MAXN][5];
int dx[] = { 0,1 };
int dy[] = { 1,0 };
int res = 0;
bool dfs(int curx, int cury) {//传入当前坐标
if (curx == n && cury == 3) {//如果当前坐标为终点，则返回true
return 1;
}
else {//否则我们分别往右或者往下，如果有一条路能走，则返回true
bool flag = 0;
for (int i = 0; i < 2; i++) {
int nx = dx[i] + curx;
int ny = dy[i] + cury;
if (nx <= n && ny <= 3 && mt[nx][ny] != -1) {
if (mt[nx][ny] == 0) {
flag = 1; continue;
}//如果下一个点可以走到终点，那么这一个点一定可以走到终点,吧flag改为1
if (dfs(nx, ny)) {//dfs下一个点是否能走到终点
flag = 1;
}
}
}
if (flag == 0) mt[curx][cury] = -1;//如果这个点不能走到终点，那么这个点直接打为-1，以后不考虑
else {
res ++;
mt[curx][cury] = 0;
}
return flag;
}
}
void solve() {
res = 0;
cin >> n >> k;
for (int i = 1; i <= n; i++) {//初始化
for (int j = 1; j <= 3; j++) mt[i][j] = 1;
}
while (k--) {//做k次
int x, y;
cin >> x >> y;
mt[x][y] = -1 * mt[x][y];
}
dfs(1, 1);//dfs得到答案
cout << res << endl;
return;
}
int main()
{
int t;
cin >> t;
while (t--) {
solve();
}
return 0;
}
H.Tokitsukaze and K-Sequence
单独考虑算贡献率
1.长度为n的序列划分成k个子序列
2.定义序列的值为这个序列中只出现一次的数字的个数
思路：
1.当某个数出现次数<=k的时候，随便找个子序列放，贡献为x
2.当某个数出现次数>k的时候，最后一个子序列放完所有的重复数字
#include<bits/stdc++.h>
using namespace std;
#define int long long
typedef long long LL;
const int mod = 233333333;
const int INF = 0x3f3f3f3f;
#define Max 500100
void solve() {
int n;
cin >> n;
int ans = 0;
map<int, int> cnt;
for (int i = 0; i < n; ++ i) {
int x;
cin >> x;
cnt[x] ++; // 记录每个数出现的次数
}
vector<int> d1(n + 1), d2(n + 1);
for (auto [_, x] : cnt) { // x 为出现次数
d1[x] += x; // x <= k 的个数取 x
d2[x - 1] ++; // x > k 的个数取 x - 1
}
for (int i = 1; i <= n; ++ i) {
d1[i] += d1[i - 1];
}
for (int i = n - 1; i >= 0; -- i) {
d2[i] += d2[i + 1];
}
// d1[] x <= k 的个数取 x ， d2[] x > k 的个数取 x - 1
for (int i = 1; i <= n; ++ i) {
auto ans = d1[i] + d2[i] * (i - 1);
cout << ans << endl;
}
}
int main(){
int t;
cin >> t;
while (t --) {
solve();
}
return 0;
}
I.Tokitsukaze and Musynx
1.n个音符从屏幕的上方移动到下方
2.当音符移动到判定线附近时点击音符，会获得一个判定分x。
3.判定分在不同的值域区间可以获得不同的 SYNC.RATE
4.在游戏中，玩家可以使用一个整数h来修正一轮游戏的所有判定分
J.Tokitsukaze and Sum of MxAb
思维题
ai和aj在数轴上的情况：
- ai<0<aj
max为ai到aj的距离
即，max为|ai|加|aj| - 0<ai<aj
max为ai加aj
即，max为|ai|加|aj| - 0>ai<aj
max为-ai加-aj
即，max为|ai|加|aj|
因为|ai|加|aj|=|aj|加|ai|
题目要求：
for(int i=0;i<n;i++)
for(int j=0;j<n;j++)
ans+=abs(a[i])+abs(a[j]);
从这个循环可以看出ai被加了2n次，因此被简化成下面：
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const ll N=1e6+100;
int main(){
int t;
cin>>t;
while(t--){
int n;
cin>>n;
ll sum=0;
for(int i=1;i<=n;i++){
ll a;
cin>>a;
sum+=2*n*abs(a);
}
cout<<sum<<endl;
}
}
Day5
A. 解开束缚缠丝Ⅱ
1.构成的最长回文串的长度是多少
2.分情况讨论，奇数的情况，偶数的情况
3.分别统计每个字符出现的次数
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
int n;
int cnt[130];
int one = 0, ans = 0;
//统计每个字母的数目。奇数有一个放中间，偶数直接放两边
LL jiejue()
{
cin >> n;
for (int i = 'a'; i <= 'z'; ++i) {
cnt[i] = 0;
}
for (int i = 'A'; i <= 'Z'; ++i) {
cnt[i] = 0;
}
for (int i = 1; i <= n; ++i) {
string x;
cin >> x;
cnt[x[0]]++;
}
one = ans = 0;
for (int i = 'A'; i <= 'Z'; ++i) {
if (cnt[i] % 2 != 0) {
one = 1;
ans += (cnt[i] - 1);
}
else ans += cnt[i];
}
for (int i = 'a'; i <= 'z'; ++i) {
if (cnt[i] % 2 != 0) {
one = 1;
ans += (cnt[i] - 1);//如果是一个的话就摆不好
}
else ans += cnt[i];
}
if(one==1){
cout << ans +1 << endl;
}
else{
cout<< ans<< endl;
}
}
int main()
{
int t;
cin>>t;
while(t--){
jiejue();
}
}
B.7的意志
1.寻找区间能相加等于7777的
2.用前缀和算出他们的前缀和，然后判断+7777的数是否在这个前缀和中
3.若在，找出他的最小下标
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const LL N=1e5+10;
LL s[N];
LL a[N];
//输出一个整数代表有多少个不同的区间和为7777
LL jiejue()
{
int n;
cin>>n;
for(int i=1;i<=n;i++){
cin>>a[i];
s[i]=s[i-1]+a[i];//前缀和
}
LL ans=0;
for(int i=1;i<=n;i++){
LL tar = s[i - 1] + 7777;//左边 i-1
LL x = lower_bound(s + 1, s + n + 1, tar) - s;//右边x
if (s[x] == tar) ++ans;
}
cout<<ans<<endl;
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
int t;
cin>>t;
while(t--){
jiejue();
}
return 0;
}
I. 好想听肆宝唱歌啊
1.关键是结构体排序
2.找到第k+1的歌曲名字
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
int n;
struct SONG {
int w;
string x;
}s[100005];//结构体
bool operator<(const SONG &A, const SONG &B) {
return A.w > B.w;
};//自定义排序规则
void jiejue() {
cin >> n;
for (int i = 1; i <= n; ++i) {
cin >> s[i].w >> s[i].x;
}
sort(s + 1, s + n + 1);
int k;
cin >> k;
cout << s[k + 1].x<<endl;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
LL t;
// cin >> _;
t= 1;
while (t--) jiejue();
return 0;
}
J. 毁灭凤凰人
1.有两种情况下能将凤凰人除外
2.送到墓地，再使用怪兽卡
3.没送到墓地，使用「墓穴的指名者」
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
int n, m;
int mxa = 0, a = 0, b = 0;
void jiejue() {
cin >> n >> m;//卡牌数量，毁灭凤凰人状态，0攻击1防守
for (int i = 1; i <= n; ++i) {
int o, x;
cin >> o;//卡牌种类。0状态附带攻击值
if (o == 0) {
cin >> x;
mxa = max(mxa, x);//只使用攻击值最大的卡牌
}
else if (o == 1) a = 1;//1状态防守，使用完0卡将怪兽送走
else b = 1;//2状态直接送走
}
if (m == 0 && mxa >= 2500 && a) {//凤凰人攻击 ，并且我们有1卡
cout << "haoye\n";
return;
}
else if (m == 1 && mxa > 2100 && a) {//凤凰人防守 ，并且我们有1卡
cout << "haoye\n";
return;
}
else if (b && n >=2) {//只要保证n有两张以上的卡就可以直接送走
cout << "haoye\n";
return;
}
else cout << "QAQ\n";
}
int main() {
ios::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
LL t;
// cin >> t;
t = 1;
while (t--) jiejue();
return 0;
}
K. 欢迎来到杭师大
直接输出
#include<bits/stdc++.h>
using namespace std;
int main()
{
int n;
cin>>n;
string s;
s="Welcome to HZNU";
while(n--)
{
cout<<s<<endl;
}
}
L. Ayanoto 变形记
任意一个大于0的数，进行有限次的相加绝对都会加到某个数
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const LL N=1e5+10;
LL n,x;
//x长度,n个点
LL jiejue(){
cin>>n>>x;
//看看是否能从0加到n
int ans=0;
if(x!=0) cout<<"yes"<<endl;
else cout<<"no"<<endl;
}
int main()
{
int t;
cin>>t;
while(t--){
jiejue();
}
return 0;
}
M. P 龙学的教诲
1.每个单词每个单词的找，看标点是否在末尾
2.按照规则输出
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const LL N=2e5;
LL n;
string x[N];
char note;
void print(int id) {//输出一整个单词
if (id != n) cout << x[id];//不等于最后一个单词
else {
int len = x[id].length();
for (int i = 0; i < len - 1; ++i) {//到len-2
cout << x[id][i];
}
}
}
LL jiejue()
{
//cin>>n;
n=0;
while (1) {
cin >> x[++n];
//遇到空格看一下末尾有没有标点
int len = x[n].length();
if (x[n][len - 1] == '.'|| x[n][len - 1] == '!' or x[n][len - 1] == '?') {
note = x[n][len - 1];//标点存这
break;//找到标点直接break
}
}
for (int i = 1; i <= n / 2; ++i) {
print(i); //1~n/2
cout << ' ';
print(n - i + 1);//n~n/2+1
if (i < n / 2 ||n % 2 == 1) cout << ' ';
}
if (n % 2 == 1){ //如果是奇数，偶数的最后一个数就是他
print(n / 2 + 1);
}
cout << note << endl;
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
int t;
cin>>t;//t行若干单词
while(t--){
jiejue();
}
return 0;
}