幼稚园的树
题目描述
牛牛在幼稚园做义工，幼稚园中共有 nnn 颗树，第 1 天中午时它们的高度分别为：h1,h2,…,hnh_1,h_2,…,h_nh1,h2,…,hn （单位：厘米）。
每一天的晚上每棵树的高度都会增加 aaa 厘米，而牛牛的任务则是在第二天的清晨检查每一颗树的高度，若某颗树的高度超过了 kkk 厘米牛牛就会将它的高度修剪为 bbb 厘米。
牛牛想请你帮它计算一下第 mmm 天中午每一颗树的高度。
输入描述:
本题采用多组案例输入，第一行一个整数 TTT 代表案例组数。
每组案例中，第一行输入一个数 nnn。
接下来一行输入 nnn 个由空格分隔的整数代表：h1,h2,…,hnh_1,h_2,…,h_nh1,h2,…,hn。
接下来一行输入三个由空格分隔的整数代表：a k ba\ k\ ba k b。
接下来一行输入一个整数代表：mmm。
保证：
0<n,m,k≤10000 < n,m,k \le 10000<n,m,k≤1000
0<hi,b≤k0 < h_i,b \le k0<hi,b≤k
0<a≤100 < a \le 100<a≤10
单个测试点中所有案例 nnn 的和与 mmm 的和都不超过 300030003000
输出描述:
#include <stdio.h>
int main(){
int b,c;
int a[3001];
scanf("%d",&b);
for(c=1;c<=b;c++)
{
int x,y,z,k,l,i,m;
scanf("%d",&x);
for(i=0;i<x;i++)
scanf("%d",&a[i]);
scanf("%d %d %d",&y,&z,&k);
scanf("%d",&l);
for(i=1;i<l;i++)
{
for(m=0;m<x;m++)
a[m]+=y;
for(m=0;m<x;m++)
{
if(a[m]>z)
a[m]=k;
}
}
printf("%d",a[0]);
for(i=1;i<x;i++)
printf(" %d",a[i]);
printf("\n");
}
}
剩下的数
牛牛有一个由 l…rl…rl…r 共 r−l+1r-l+1r−l+1 个整数组成的环。
牛妹对这个数环进行了 mmm 次询问，每次给定一个整数 xxx 问牛牛操作到不能继续操作时最少会剩下几个数。
每一次操作，牛牛都会选择环上一段（可以是整个环），这一段数的和应该为 xxx 的倍数，然后牛牛就会删去这一段，同时把剩下的数按顺序重新连成一个环。
输入描述:
本题采用多组案例输入，第一行一个整数 TTT 代表案例组数。
每组案例中，第一行输入两个空格分隔的整数：l rl\ rl r 。
接下来一行输入一个整数 mmm 。
接下来 mmm 行，每行输入一个数 xxx 代表询问。
保证：
0<l<r<1090 < l < r < 10^90<l<r<109
0<x≤(r−l+1)0 < x \le (r - l + 1)0<x≤(r−l+1)
单个测试点中所有案例 mmm 的和不超过 10510^5105
输出描述:
对于每组案例，输出共 mmm 行，每行一个整数代表牛妹询问的答案。
#include <stdio.h>
int main()
{
int t;
scanf("%d",&t);
while(t--)
{
long long l,r,x,m,sum=0;
scanf("%lld%lld%lld",&l,&r,&m);
sum=(l+r)*(r-l+1)/2;
while(m--)
{
scanf("%lld",&x);
if(sum%x==0)printf("0\n");
else printf("1\n");
}
}
}
数组划分
#include<stdio.h>
int main()
{
long n,a[100000]={0},b[100000]={0},h[1000000]={0},p;
scanf("%ld",&n);
for(int i=0;i<n;i++)
{
scanf("%ld",&a[i]);
p=a[i];
h[p]=1;
for(int j=2;j*j<=a[i];j++)
{
while(a[i]%j==0)
{a[i]=a[i]/j;
h[j]=1;}
p=a[i];
h[p]=1;
}
}
for(int i=0;i<n;i++)
{
scanf("%ld",&b[i]);
for(int j=2;j*j<b[i];j++)
{
if(b[i]%j==0&&h[j]==1)
{ printf("No\n");
return 0;
}
else if(h[b[i]]==1)
{ printf("No\n");
return 0;
}
}
}
printf("Yes\n");
return 0;
}
子树的大小
#include<stdio.h>
#include<math.h>
long long num=0;
long long min(long long a,long long b)
{
return a>b?b:a;
}
long long n,k,m,T,q;
void p(long long l,long long r)
{
if(l>=n)return;
r=min(n-1,r);
num+=(r-l+1);
p(l*k+1,r*k+k);
}
int main()
{
scanf("%lld",&T);
while(T)
{
scanf("%lld %lld %lld",&n,&k,&m);
while(m)
{
long long sum=0;
scanf("%lld",&q);
if(k==1)
{
printf("%lld\n",n-q);
m--;
continue;
}
p(q,q);
printf("%lld\n",num);
num=0;
m--;
}
T--;
}
}
剖分
#include "iostream"
#include "vector"
#include "string"
#include "utility"
#include "queue"
#include "set"
#include "map"
#include "unordered_map"
#include "algorithm"
#include "cstring"
#include "stack"
#include "cmath"
#include "numeric"
#include "cassert"
using namespace std;
typedef long long ll;
const int N = 1e5 + 7;
const ll INF = 0x3f3f3f3f3f3f3f3f;
const ll MOD = 1e9 + 7;
int main() {
#ifndef ONLINE_JUDGE
freopen("in.txt", "r", stdin);
#endif
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n, m;
cin >> n >> m;
vector<int> root(n + 1, 0), node(n + 1, 0);
vector<int> ans(m + 1, 0);
for (int i = 0; i < m; i++) {
int op, x;
cin >> op >> x;
if (op == 1) {
root[x]++;
} else if (op == 2) {
root[1]++;
root[x]--;
} else if (op == 3) {
while (x) {
node[x]++;
x /= 2;
}
} else {
root[1]++;
while (x) {
node[x]--;
x /= 2;
}
}
}
for (int i = 1; i <= n; i++) {
ans[root[i] + node[i]]++;
if (i * 2 <= n) root[i * 2] += root[i];
if (i * 2 + 1 <= n) root[i * 2 + 1] += root[i];
}
for (int i = 0; i <= m; i++)
cout << ans[i] << " ";
return 0;
}
子串的子序列
#include <bits/stdc++.h>
using namespace std;
const int N = 500009;
#define ll long long
ll f[N][3][2][2]; /// 有效区域：000,100,110,200,201,210,211
char s[N];
int main() {
scanf("%s", s + 1);
ll ans = 0;
for(int i = 1; i <= strlen(s + 1); i ++) {
if(s[i] == 'a') {
f[i][0][0][0] = 0;
f[i][1][0][0] = f[i - 1][1][1][0];
f[i][1][1][0] = f[i - 1][1][0][0] + f[i - 1][0][0][0] + 1;
f[i][2][0][0] = f[i - 1][2][1][0];
f[i][2][0][1] = f[i - 1][2][1][1];
f[i][2][1][0] = f[i - 1][2][0][0];
f[i][2][1][1] = f[i - 1][2][0][1];
} else if(s[i] == 'c') {
f[i][0][0][0] = f[i - 1][0][0][0] + 1;
f[i][1][0][0] = 0;
f[i][1][1][0] = 0;
f[i][2][0][0] = f[i - 1][1][0][0] + f[i - 1][2][0][0];
f[i][2][0][1] = f[i - 1][2][0][1];
f[i][2][1][0] = f[i - 1][2][1][1];
f[i][2][1][1] = f[i - 1][1][1][0] + f[i - 1][2][1][0];
} else {
f[i][0][0][0] = f[i - 1][0][0][0] + 1;
f[i][1][0][0] = f[i - 1][1][0][0];
f[i][1][1][0] = f[i - 1][1][1][0];
f[i][2][0][0] = f[i - 1][2][0][0];
f[i][2][0][1] = f[i - 1][2][0][1];
f[i][2][1][0] = f[i - 1][2][1][0];
f[i][2][1][1] = f[i - 1][2][1][1];
}
ans += f[i][2][1][0] + f[i][2][0][0];
}
cout << ans;
return 0;
}
