本地小黑板，学习不迷路
#include<iostream>
#include<cstring>
#include<queue>
using namespace std;
int n,p,c,head[1010],k=0,f[1010],v[1010],sum[1010],ans=2e9+10;
//sum[i]表示牧场i有多少头牛
struct node{
int to,v,nxt;
}a[3010];
void add(int x,int y,int z){
k++;a[k]={y,z,head[x]};head[x]=k;
}
void dij(int s){ //计算起点s的最短路
priority_queue<pair<int,int> > q; //存<距离，结点编号>
q.push({0,s}); //起点入队 <距离0，编号s>
while(q.size()){
int x=q.top().second; //起点的编号
q.pop(); //起点出队
if(v[x]) continue;
v[x]=1; //确定点x的最短路，并且用x松弛
for(int i=head[x];i;i=a[i].nxt){ //遍历x可以到达的所有边
int to=a[i].to, w=a[i].v;
if(f[x]+w<f[to]){ //松弛操作
f[to]=f[x]+w;
q.push({-f[to],to}); //起点到to的距离和编号入队
}
}
}
}
int main(){
cin>>n>>p>>c;
for(int i=1;i<=n;i++){
int x;cin>>x;
sum[x]++; //统计牧场x有多少头牛
}
for(int i=1;i<=c;i++){
int x,y,z;
cin>>x>>y>>z;
add(x,y,z);add(y,x,z); //无向图，双向建边
}
for(int i=1;i<=p;i++){ //枚举每个牧场作为起点
memset(f,0x3f,sizeof f);
memset(v,0,sizeof v);
f[i]=0; //起点到起点的最短路为0
dij(i); //以i为起点，计算最短路
int dis=0;
for(int j=1;j<=p;j++) dis+=sum[j]*f[j]; //牧场i的牛数*距离
ans=min(ans,dis);
}
cout<<ans;
return 0;
}
/* Problem: 香甜的黄油
Language: C++ Result: 正确 Time: 2026-10-10 21:01:33
User: admin Problem: 1774 contest_id: 1184*/
#include<iostream>
#include<cstring>
#include<queue>
using namespace std;
int n,p,c,head[1010],k=0,f[1010],v[1010],sum[1010],ans=2e9+10;
//sum[i]表示牧场i有多少头牛
struct node{
int to,v,nxt;
}a[3010];
void add(int x,int y,int z){
k++;a[k]={y,z,head[x]};head[x]=k;
}
void dij(int s){ //计算起点s的最短路
priority_queue<pair<int,int> > q; //存<距离，结点编号>
q.push({0,s}); //起点入队 <距离0，编号s>
while(q.size()){
int x=q.top().second; //起点的编号
q.pop(); //起点出队
if(v[x]) continue;
v[x]=1; //确定点x的最短路，并且用x松弛
for(int i=head[x];i;i=a[i].nxt){ //遍历x可以到达的所有边
int to=a[i].to, w=a[i].v;
if(f[x]+w<f[to]){ //松弛操作
f[to]=f[x]+w;
if(v[to]==0){
q.push({-f[to],to}); //起点到to的距离和编号入队
}
}
}
}
}
int main(){
cin>>n>>p>>c;
for(int i=1;i<=n;i++){
int x;cin>>x;
sum[x]++; //统计牧场x有多少头牛
}
for(int i=1;i<=c;i++){
int x,y,z;
cin>>x>>y>>z;
add(x,y,z);add(y,x,z); //无向图，双向建边
}
for(int i=1;i<=p;i++){ //枚举每个牧场作为起点
memset(f,0x3f,sizeof f);
memset(v,0,sizeof v);
f[i]=0; //起点到起点的最短路为0
dij(i); //以i为起点，计算最短路
int dis=0;
for(int j=1;j<=p;j++) dis+=sum[j]*f[j]; //牧场i的牛数*距离
ans=min(ans,dis);
}
cout<<ans;
return 0;
}
/* Problem: 香甜的黄油
Language: C++ Result: 正确 Time: 2026-10-10 20:59:57
User: admin Problem: 1774 contest_id: 1184*/
#include<iostream>
#include<cstring>
using namespace std;
int n,m,s,e,ans=0,head[2510],k=0,f[2510],v[2510];//邻接表：链式前向星
//f[i]表示起点到i的最短路，v[i]=1表示起点到i的最短路已经确定
//a[i][j]表示结点i和结点j之间的路径长度
struct node{
int to,v,nxt;
}a[20010];
void add(int x,int y,int z){
k++,a[k]={y,z,head[x]},head[x]=k; //e[k].to=y,e[k].v=z,e[k].nxt=head[x]
}
void diskstra(){
for(int i=1;i<=n;i++){ //确定n次最短距离
int mi=0,minn=0x3f3f3f3f;
for(int j=1;j<=n;j++){
if(!v[j]&&f[j]<minn){ //在没有被确定最短路的结点里面，打擂台找最短距离
mi=j;
minn=f[j];
}
}
if(mi) v[mi]=1; //结点mi的最短路被确定
for(int j=head[mi];j;j=a[j].nxt){ //使用mi进行松弛操作
int to=a[j].to;
if(!v[to]&&a[j].v){
f[to]=min(f[to],f[mi]+a[j].v); //松弛操作：使用起点到mi的最短路 更新 起点到j的最短路
}
}
}
}
int main(){
cin>>n>>m>>s>>e;
for(int i=1;i<=m;i++){
int x,y,z; cin>>x>>y>>z;
add(x,y,z);
add(y,x,z);//无向图，双向建边
}
memset(f,0x3f,sizeof f); //起点到每个点的初始距离为无穷大，表示不可到达
f[s]=0; //起点到起点的距离初始化为0
diskstra();
cout<<f[e]; //输出s到e的最短路
return 0;
}
/*
单源最短路：无负环
*/
/* Problem: 热浪
Language: C++ Result: 正确 Time: 2026-10-10 20:10:52
User: admin Problem: 1367 contest_id: 1184*/
#include<iostream>
#include<cstring>
using namespace std;
int n,m,s,e,ans=0,a[2510][2510],f[2510],v[2510];//邻接矩阵
//f[i]表示起点到i的最短路，v[i]=1表示起点到i的最短路已经确定
//a[i][j]表示结点i和结点j之间的路径长度
void diskstra(){
for(int i=1;i<=n;i++){ //确定n次最短距离
int mi=0,minn=0x3f3f3f3f;
for(int j=1;j<=n;j++){
if(!v[j]&&f[j]<minn){ //在没有被确定最短路的结点里面，打擂台找最短距离
mi=j;
minn=f[j];
}
}
if(mi) v[mi]=1; //结点mi的最短路被确定
for(int j=1;j<=n;j++){ //使用mi进行松弛操作
if(!v[j]&&a[mi][j]){
f[j]=min(f[j],f[mi]+a[mi][j]); //松弛操作：使用起点到mi的最短路 更新 起点到j的最短路
}
}
}
}
int main(){
cin>>n>>m>>s>>e;
for(int i=1;i<=m;i++){
int x,y,z; cin>>x>>y>>z;
a[x][y]=z;
a[y][x]=z; //无向图，双向建边
}
memset(f,0x3f,sizeof f); //起点到每个点的初始距离为无穷大，表示不可到达
f[s]=0; //起点到起点的距离初始化为0
diskstra();
cout<<f[e]; //输出s到e的最短路
return 0;
}
/*
单源最短路：无负环
*/
/* Problem: 热浪
Language: C++ Result: 正确 Time: 2026-10-10 19:37:19
User: admin Problem: 1367 contest_id: 1184*/
#include <string>
#include <iostream>
using namespace std;
int main() { //注意：替换ans中的字符ABCD，不要空格，不要写错了答案顺序
string ans =
"BCBAB"
"BCDAB"
"AACDD"
"AABAB"
"AABAA";
int no;
cin>>no;
cout<<ans[no - 1];
return 0;
}
/* Problem: 选择题判断题8
Language: C++ Result: 正确 Time: 2026-10-08 18:12:34
User: admin Problem: 5162 contest_id: 0*/
#include <string>
#include <iostream>
using namespace std;
int main() { //注意：替换ans中的字符ABCD，不要空格，不要写错了答案顺序
string ans =
"CDCBA"
"BADCB"
"ADDBC"
"ABBAA"
"BABAB";
int no;
cin>>no;
cout<<ans[no - 1];
return 0;
}
/* Problem: 选择题判断题7
Language: C++ Result: 正确 Time: 2026-10-08 18:10:24
User: admin Problem: 5161 contest_id: 0*/
#include <string>
#include <iostream>
using namespace std;
int main() { //注意：替换ans中的字符ABCD，不要空格，不要写错了答案顺序
string ans =
"BACBC"
"BADCB"
"BCBCA"
"BBBAA"
"AABAB";
int no;
cin>>no;
cout<<ans[no - 1];
return 0;
}
/* Problem: 选择题判断题6
Language: C++ Result: 正确 Time: 2026-10-08 18:08:05
User: admin Problem: 5160 contest_id: 0*/
#include <string>
#include <iostream>
using namespace std;
int main() { //注意：替换ans中的字符ABCD，不要空格，不要写错了答案顺序
string ans =
"ACBCD"
"BADCB"
"DADCC"
"ABAAB"
"ABABB";
int no;
cin>>no;
cout<<ans[no - 1];
return 0;
}
/* Problem: 选择题判断题5
Language: C++ Result: 正确 Time: 2026-10-08 18:05:31
User: admin Problem: 5159 contest_id: 0*/
#include <string>
#include <iostream>
using namespace std;
int main() { //注意：替换ans中的字符ABCD，不要空格，不要写错了答案顺序
string ans =
"CBBCA"
"DCCCC"
"BDBCA"
"ABABA"
"BABAB";
int no;
cin>>no;
cout<<ans[no - 1];
return 0;
}
/* Problem: 选择题判断题4
Language: C++ Result: 正确 Time: 2026-10-08 18:02:09
User: admin Problem: 5158 contest_id: 0*/
#include <string>
#include <iostream>
using namespace std;
int main() { //注意：替换ans中的字符ABCD，不要空格，不要写错了答案顺序
string ans =
"DDACB"
"CDCAA"
"DCDBB"
"BBBBB"
"BBAAB";
int no;
cin>>no;
cout<<ans[no - 1];
return 0;
}
/* Problem: 选择题判断题3
Language: C++ Result: 正确 Time: 2026-10-08 17:59:31
User: admin Problem: 5157 contest_id: 0*/
#include <string>
#include <iostream>
using namespace std;
int main() { //注意：替换ans中的字符ABCD，不要空格，不要写错了答案顺序
string ans =
"CBADA"
"CBDBD"
"DCAAA"
"AABBB"
"ABABB";
int no;
cin>>no;
cout<<ans[no - 1];
return 0;
}
/* Problem: 选择题判断题2
Language: C++ Result: 正确 Time: 2026-10-08 17:56:41
User: admin Problem: 5156 contest_id: 0*/
#include <string>
#include <iostream>
using namespace std;
int main() { //注意：替换ans中的字符ABCD，不要空格，不要写错了答案顺序
string ans =
"CDAAB"
"CDACD"
"DBAAD"
"ABBAA"
"AABBB";
int no;
cin>>no;
cout<<ans[no - 1];
return 0;
}
/* Problem: 选择题判断题1
Language: C++ Result: 正确 Time: 2026-10-08 17:52:00
User: admin Problem: 5155 contest_id: 0*/
#include <string>
#include <iostream>
using namespace std;
int main() { //注意：替换ans中的字符ABCD，不要空格，不要写错了答案顺序
string ans =
"BBCAC"
"DAADA"
"CBBCD"
"AABBA"
"BAABA";
int no;
cin>>no;
cout<<ans[no - 1];
return 0;
}
/* Problem: 选择题判断题8
Language: C++ Result: 正确 Time: 2026-10-08 14:35:42
User: admin Problem: 4886 contest_id: 0*/
#include <string>
#include <iostream>
using namespace std;
int main() { //注意：替换ans中的字符ABCD，不要空格，不要写错了答案顺序
string ans =
"BACDC"
"CDAAC"
"DBBBD"
"BBBAB"
"AABAA";
int no;
cin>>no;
cout<<ans[no - 1];
return 0;
}
/* Problem: 选择题判断题7
Language: C++ Result: 正确 Time: 2026-10-08 14:27:27
User: admin Problem: 4885 contest_id: 0*/
#include <string>
#include <iostream>
using namespace std;
int main() { //注意：替换ans中的字符ABCD，不要空格，不要写错了答案顺序
string ans =
"DBCAA"
"BAABB"
"DBABA"
"BBBAB"
"BABAA";
int no;
cin>>no;
cout<<ans[no - 1];
return 0;
}
/* Problem: 选择题判断题6
Language: C++ Result: 正确 Time: 2026-10-08 14:21:55
User: admin Problem: 4884 contest_id: 0*/
#include <cstdio>
#include <algorithm>
#include <queue>
using namespace std;
const int N = 505;
const int E = 1005;
const int oo = 1e9;
int n, m;
int h[N], to[E], nx[E], l[E], t[E];
int d[N][N];
priority_queue<pair<int, int> > q;
void calc(int u, int d[]) {
for (int i = 1; i <= n; i++)
d[i] = -oo;
d[u] = oo;
q.push(make_pair(d[u], u));
while (!q.empty()) {
pair<int, int> p = q.top();
q.pop();
if (d[p.second] != p.first)
continue;
int u = p.second;
for (int i = h[u]; i; i = nx[i]) {
int v = to[i];
int w = min(d[u] - t[i], l[i]);
if (w < 0)
continue;
if (w > d[v]) {
d[v] = w;
q.push(make_pair(d[v], v));
}
}
}
}
int main() {
int q;
scanf("%d%d%d", &n, &m, &q);
for (int i = 1; i <= m; i++) {
int u, v;
scanf("%d%d%d%d", &u, &v, &l[i], &t[i]);
to[i] = u;
nx[i] = h[v];
h[v] = i;
}
for (int i = 1; i <= n; i++)
calc(i, d[i]);
while (q--) {
int u, v, s;
scanf("%d%d%d", &u, &v, &s);
if (s <= d[v][u])
printf("Yes\n");
else
printf("No\n");
}
return 0;
}
/* Problem: 末班车
Language: C++ Result: 正确 Time: 2026-10-08 09:36:07
User: admin Problem: 5154 contest_id: 0*/
#include <cstdio>
#include <algorithm>
using namespace std;
const int N = 1e5 + 5;
const int E = N << 1;
const int mod = 998244353;
int n, m;
int h[N], to[E], nx[E], et;
int d[N];
int ans;
void ae(int u, int v) {
to[++et] = v;
nx[et] = h[u];
h[u] = et;
}
void dfs(int u, int p=0) {
d[u] = d[p] + 1;
for (int i = h[u]; i; i = nx[i]) {
int v = to[i];
if (v == p)
continue;
if (!d[v])
dfs(v, u);
if (d[v] < d[u])
ans = 1ll * ans * (d[u] - d[v] + 1) % mod;
}
}
int main() {
scanf("%d%d", &n, &m);
for (int i = 1; i <= m; i++) {
int u, v;
scanf("%d%d", &u, &v);
ae(u, v);
ae(v, u);
}
ans = 1;
dfs(1);
printf("%d\n", ans);
return 0;
}
/* Problem: 生成树计数
Language: C++ Result: 正确 Time: 2026-10-08 09:36:06
User: admin Problem: 5153 contest_id: 0*/
#include <cstdio>
#include <algorithm>
using namespace std;
const int N = 2005;
const int mod = 1e9;
int n;
char s[N];
int f[N][N];
int main() {
scanf("%d", &n);
scanf("%s", s + 1);
f[0][0] = 1;
for (int i = 1; i <= n; i++)
for (int j = 0; j <= n; j++) {
f[i][j] = f[i - 1][j];
if (s[i] == '(' && j)
f[i][j] = (f[i][j] + f[i - 1][j - 1]) % mod;
if (s[i] == ')' && j < n)
f[i][j] = (f[i][j] + f[i - 1][j + 1]) % mod;
}
printf("%d\n", f[n][0]);
return 0;
}
/* Problem: 括号序列2
Language: C++ Result: 正确 Time: 2026-10-08 09:36:06
User: admin Problem: 5152 contest_id: 0*/
#include <cstdio>
#include <algorithm>
using namespace std;
const int N = 1005;
const int E = 2005;
int n, m;
int h[N], to[E], nx[E], et;
int id[N], od[N];
bool vis[N];
int q[N], ql, qr;
int ans[N], cnt;
bool chk(int ban) {
ql = qr = 0;
for (int i = 1; i <= n; i++) {
vis[i] = (i == ban);
if (!vis[i] && !id[i]) {
q[++qr] = i;
vis[i] = 1;
}
}
while (ql < qr) {
int u = q[++ql];
for (int i = h[u]; i; i = nx[i]) {
int v = to[i];
if (vis[v])
continue;
if (!od[v])
return 0;
q[++qr] = v;
vis[v] = 1;
}
}
return 1;
}
int main() {
scanf("%d%d", &n, &m);
for (int i = 1; i <= m; i++) {
int u, v;
scanf("%d%d", &u, &v);
to[++et] = v;
nx[et] = h[u];
h[u] = et;
od[u]++;
id[v]++;
}
for (int i = 1; i <= n; i++)
if (chk(i))
ans[++cnt] = i;
printf("%d\n", cnt);
for (int i = 1; i <= cnt; i++)
printf("%d%c", ans[i], " \n"[i == cnt]);
return 0;
}
/* Problem: 必经之路
Language: C++ Result: 正确 Time: 2026-10-08 09:36:05
User: admin Problem: 5151 contest_id: 0*/
#include <cstdio>
#include <algorithm>
using namespace std;
const int N = 2e4 + 5;
const int E = N << 1;
int n;
int h[N], to[E], nx[E], et;
int ans;
void ae(int u, int v) {
et++;
to[et] = v;
nx[et] = h[u];
h[u] = et;
}
int dfs(int u, int p=0) {
int sz = 1;
for (int i = h[u]; i; i = nx[i])
if (to[i] != p)
sz += dfs(to[i], u);
ans = min(ans, abs(n - 2 * sz));
return sz;
}
int main() {
scanf("%d", &n);
for (int i = 1; i < n; i++) {
int u, v;
scanf("%d%d", &u, &v);
ae(u, v);
ae(v, u);
}
ans = n;
dfs(1);
printf("%d\n", ans);
return 0;
}
/* Problem: 分树规划
Language: C++ Result: 正确 Time: 2026-10-08 09:36:05
User: admin Problem: 5150 contest_id: 0*/
#include <cstdio>
#include <algorithm>
using namespace std;
const int N = 2005;
const long long oo = 1e18;
int n;
int a[N], pre[N];
long long f[N];
int main() {
scanf("%d", &n);
for (int i = 1; i <= n; i++) {
scanf("%d", &a[i]);
pre[i] = pre[i - 1] + a[i];
}
for (int i = 1; i <= n; i++) {
f[i] = oo;
for (int j = 0; j < i; j++)
f[i] = min(f[i], f[j] + 1ll * (pre[i] - pre[j]) * (pre[i] - pre[j]));
}
printf("%lld\n", f[n]);
return 0;
}
/* Problem: 数组划分2
Language: C++ Result: 正确 Time: 2026-10-08 09:36:05
User: admin Problem: 5149 contest_id: 0*/
#include <cstdio>
#include <algorithm>
using namespace std;
const int N = 2005;
int n, t;
int v[N], s[N], p[N];
double ans;
bool cmp(int x, int y) {
return s[x] < s[y];
}
int main() {
scanf("%d%d", &n, &t);
for (int i = 1; i <= n; i++) {
scanf("%d%d", &v[i], &s[i]);
p[i] = i;
}
sort(p + 1, p + n + 1, cmp);
int ss = 0, sv = 0;
for (int i = 1; i <= n; i++) {
int cv = v[p[i]], cs = s[p[i]];
if (ss + cs * cv > t * (sv + cv)) {
double k = (double)(t * sv - ss) / (cs - t);
ans = max(ans, sv + k);
break;
}
ss += cs * cv;
sv += cv;
}
if (ss == sv * t) ans = max(ans, (double) sv);
sv = ss = 0;
for (int i = n; i >= 1; i--) {
int cv = v[p[i]], cs = s[p[i]];
if (ss + cs * cv < t * (sv + cv)) {
double k = (double)(t * sv - ss) / (cs - t);
ans = max(ans, sv + k);
break;
}
ss += cs * cv;
sv += cv;
}
if (ss == sv * t) ans = max(ans, (double) sv);
printf("%.3lf\n", ans);
return 0;
}
/* Problem: 饮品调制
Language: C++ Result: 正确 Time: 2026-10-08 09:36:05
User: admin Problem: 5148 contest_id: 0*/
#include <cstdio>
using namespace std;
int n, ans;
bool not_prime[1000005];
int primes[500000], pcnt = 0;
void get_primes() {
not_prime[1] = true;
for (int i = 2; i <= n; ++i) {
if (!not_prime[i]) {
primes[pcnt++] = i;
for (int j = 2; i * j <= n; ++j) {
not_prime[i * j] = true;
}
}
}
}
int main() {
scanf("%d", &n);
get_primes();
for (int i = 0; i < pcnt && primes[i] <= n / 2; ++i)
if (!not_prime[n - primes[i]])
ans++;
printf("%d\n", ans);
return 0;
}
/* Problem: 哥德巴赫猜想2
Language: C++ Result: 正确 Time: 2026-10-08 09:36:05
User: admin Problem: 5147 contest_id: 0*/
#include <cstdio>
#include <algorithm>
using namespace std;
const int N = 15;
int n, m;
int a[N][N];
void sort_row(int n) {
for (int i = 1; i <= m; i++)
for (int j = 1; j < m; j++)
if (a[n][j] > a[n][j + 1]) {
int tmp = a[n][j];
a[n][j] = a[n][j + 1];
a[n][j + 1] = tmp;
}
return;
}
void sort_col(int m) {
for (int i = 1; i <= n; i++)
for (int j = 1; j < n; j++)
if (a[j][m] > a[j + 1][m]) {
int tmp = a[j][m];
a[j][m] = a[j + 1][m];
a[j + 1][m] = tmp;
}
return;
}
int main() {
scanf("%d%d", &n, &m);
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++)
sort_row(i);
for (int i = 1; i <= m; i++)
sort_col(i);
for (int i = 1; i <= n; i++)
for (int j = 1; j <= m; j++)
printf("%d%c", a[i][j], " \n"[j == m]);
return 0;
}
/* Problem: 有序网格
Language: C++ Result: 正确 Time: 2026-10-08 09:36:05
User: admin Problem: 5146 contest_id: 0*/
#include <iostream>
using namespace std;
int f[22], g[22];
int main() {
int n;
cin >> n;
for (int i = 1; i <= n; ++i) {
f[i] = 2 * g[i - 1] + 1;
g[i] = 2 * g[i - 1] + f[i - 1] + 2;
}
cout << g[n] << endl;
return 0;
}
/* Problem: 新汉诺塔
Language: C++ Result: 正确 Time: 2026-10-08 09:36:05
User: admin Problem: 5145 contest_id: 0*/
#include <iostream>
#include <string>
using namespace std;
int main() {
string s = "";
getline(cin, s);
for (int k = 1;; ++k) {
string spaces = "";
for (int i = 0; i < k; ++i) {
spaces += " ";
}
int pos = s.find(spaces);
if (pos < 0 || pos >= s.size()) break;
for (int i = 0; i < pos; ++i) {
cout << s[i];
}
cout << endl;
string rest = "";
for (int i = pos + k; i < s.length(); ++i) {
rest += s[i];
}
s = rest;
}
cout << s << endl;
return 0;
}
/* Problem: 分割字符串
Language: C++ Result: 正确 Time: 2026-10-08 09:36:05
User: admin Problem: 5144 contest_id: 0*/
#include <iostream>
using namespace std;
int a[20010];
int main() {
int n;
cin >> n;
for (int i = 0; i < n; ++i)
cin >> a[i];
int S = a[0];
for (int i = 1; i < n; ++i)
S &= a[i];
int ans = 0;
while (S > 0) {
if (S & 1) ans++;
S >>= 1;
}
cout << ans;
return 0;
}
/* Problem: 公共二进制位
Language: C++ Result: 正确 Time: 2026-10-08 09:36:04
User: admin Problem: 5143 contest_id: 0*/
#include <iostream>
using namespace std;
int main() {
int a, b, c, p = 0;
cin >> a >> b >> c;
for (int i = 1; i <= 8; ++i) {
for (int j = 1; j <= 16; ++j) {
++p;
if (p == a)
cout << (char)a;
else if (p == b)
cout << (char)b;
else if (p == c)
cout << (char)c;
else
cout << '*';
}
cout << '\n';
}
return 0;
}
/* Problem: 字符变换
Language: C++ Result: 正确 Time: 2026-10-08 09:36:04
User: admin Problem: 5142 contest_id: 0*/
#include <iostream>
#include <cmath>
using namespace std;
int main() {
double a, b, U;
cin >> a >> b >> U;
int ans = 1;
if (a <= U) ans++;
while (b <= U) {
ans++;
double t = sqrt(a * a + b * b);
a = b, b = t;
}
cout << ans << endl;
return 0;
}
/* Problem: 直角三角形2
Language: C++ Result: 正确 Time: 2026-10-08 09:36:04
User: admin Problem: 5141 contest_id: 0*/
#include <cstdio>
#include <algorithm>
using namespace std;
int n;
long long f, ans;
int main() {
scanf("%d", &n);
f = 1;
for (int i = 1; i <= n; i++) {
ans += f;
f *= 2;
}
printf("%lld\n", ans);
return 0;
}
/* Problem: 棋盘上的奖赏
Language: C++ Result: 正确 Time: 2026-10-08 09:36:04
User: admin Problem: 5140 contest_id: 0*/
#include <iostream>
#include <cstdio>
using namespace std;
int main() {
float t1, v, t2;
cin >> t1 >> v >> t2;
float tt = 1000.0 / v + t2;
if (tt < t1)
printf("rabbit\n");
else if (tt > t1)
printf("turtle\n");
else
printf("tie\n");
printf("%.2f\n", tt);
return 0;
}
/* Problem: 新龟兔赛跑
Language: C++ Result: 正确 Time: 2026-10-08 09:36:04
User: admin Problem: 5139 contest_id: 0*/
#include<iostream>
using namespace std;
long long n,a[200010],b[200010],f[200010];
int main(){
cin>>n;
for(int i=1;i<=n;i++) cin>>a[i];
for(int i=1;i<=n;i++) cin>>b[i];
for(int i=n;i;i--){ //从后往前推
f[i]=max(a[i]+f[i+max(1ll,b[i])],f[i+1]);
}
cout<<f[1]; //答案
return 0;
}
/*
f[i]表示从n-i选数字的最大得分之和，不见得一定选择了ai
状态转移：f[i]=max(a[i]+f[i+b[i]],f[i+1]);
*/
/* Problem: 选数
Language: C++ Result: 正确 Time: 2026-10-07 11:24:15
User: admin Problem: 4858 contest_id: 0*/
#include<iostream>
using namespace std;
long long n,f[100010],a[100010];
string s;
//f[i]表示前i个字符划分后的最大价值
int main(){
cin>>n>>s;
s=" "+s;
for(int i=1;i<=n;i++) cin>>a[i];
for(int i=1;i<=n;i++){
int cnt=0;
for(int j=i;j>=1;j--){
int x=1<<(s[j]-'a'); //s[j]占用第x位的二进制数字
if(cnt&x) break; //字符s[j]出现过
cnt|=x; //状态压缩，用二进制记录哪个字符出现过
f[i]=max(f[i],f[j-1]+a[i-j+1]); //状态转移
}
}
cout<<f[n];
return 0;
}
/* Problem: 划分字符串
Language: C++ Result: 正确 Time: 2026-10-07 10:40:03
User: admin Problem: 4505 contest_id: 0*/
#include<iostream>
using namespace std;
int n,ans=0,f[1010],a[1010];
//f[i]表示前i个人的最大积极性之和
int main(){
cin>>n;
for(int i=1;i<=n;i++) cin>>a[i],f[i]=a[i];//初始化
for(int i=1;i<=n;i++){
for(int j=1;j<i;j++){ //状态转移
f[i]=max(f[i],f[j]+a[i-j]);
}
}
cout<<f[n];//答案
return 0;
}
/* Problem: 学习小组
Language: C++ Result: 正确 Time: 2026-10-07 10:15:42
User: admin Problem: 4465 contest_id: 0*/
#include<iostream>
using namespace std;
const long long MOD=1000000007;
long long n,a,b,c,ans[200010];
//记忆化搜索：ans[i]表示数字i的方案数
long long f(long long n){
if(n<=c) return 1;
if(ans[n]) return ans[n];
ans[n]=(f(n-a)+f(n-b))%MOD;
return ans[n];
}
int main(){
cin>>n>>a>>b>>c;
cout<<f(n);
return 0;
}
/* Problem: 游戏
Language: C++ Result: 正确 Time: 2026-10-07 09:59:03
User: admin Problem: 4075 contest_id: 0*/
#include<iostream>
using namespace std;
const long long MOD=1000000007;
long long n,a,b,c,f[200010];
//状态定义：f[i]表示数字i的方案数
int main(){
cin>>n>>a>>b>>c;
for(int i=0;i<=c;i++) f[i]=1; //状态初始值
for(int i=c+1;i<=n;i++){
if(i>=a&&i>=b) f[i]=(f[i-a]+f[i-b])%MOD;
else if(i>=a) f[i]=(f[i-a]+1)%MOD;
else if(i>=b) f[i]=(f[i-b]+1)%MOD;
else f[i]=2;
}
cout<<f[n];
return 0;
}
/* Problem: 游戏
Language: C++ Result: 正确 Time: 2026-10-07 09:58:50
User: admin Problem: 4075 contest_id: 0*/
#include<iostream>
using namespace std;
const long long MOD=1000000007;
long long n,a,b,c,ans[200010];
//记忆化搜索：ans[i]表示数字i的方案数
long long f(long long n){
if(ans[n]) return ans[n];
if(n<=c) return 1;
ans[n]=(f(n-a)+f(n-b))%MOD;
return ans[n];
}
int main(){
cin>>n>>a>>b>>c;
cout<<f(n);
return 0;
}
/* Problem: 游戏
Language: C++ Result: 正确 Time: 2026-10-07 09:49:11
User: admin Problem: 4075 contest_id: 0*/
#include<iostream>
#include<algorithm>
#include<cmath>
using namespace std;
int n,m,k,ans=0,f[1010];
//f[i]表示走到方块i时，已经穿越的方块最大数量(包括i)
struct node{
int x,y;
}a[1010];
bool cmp(node n1,node n2){ //坐标小的排前面
if(n1.x==n2.x) n1.y<n2.y;
return n1.x<n2.x;
}
int main(){
cin>>n>>m>>k;
for(int i=1;i<=k;i++) cin>>a[i].x>>a[i].y;
sort(a+1,a+k+1,cmp); //排序：确保状态转移时，能转移到i的j都在i前面
for(int i=1;i<=k;i++){ //从前往后遍历每个可穿越的方块
f[i]=1; //自己可以穿越，初始值为1
for(int j=1;j<i;j++){ //方块i是否可以续在方块j的后面
if(a[i].y>a[j].y&&a[i].x>a[j].x){
f[i]=max(f[i],f[j]+1);
}
}
ans=max(ans,f[i]);//ans表示全程可以穿越的最大方块数量
}
int res=round(n*100+m*100-ans*(200-sqrt(20000)));
cout<<res;
return 0;
}
/* Problem: 飞翔
Language: C++ Result: 正确 Time: 2026-10-06 16:52:29
User: admin Problem: 1381 contest_id: 0*/
#include<iostream>
#include<queue>
#include<algorithm>
using namespace std;
int n,ans=0,e=-1;
struct node{
int s,t,id; //s达到时间，t吃草时间，id资历（数字小，资历老）
friend bool operator<(node n1,node n2){
return n1.id>n2.id; //资历数字小的排前面（数字小，资历老）
}
}a[100010];
bool cmp(node n1,node n2){
return n1.s<n2.s; //到达时间小的排前面
}
priority_queue<node> q;
int main(){
cin>>n;
for(int i=1;i<=n;i++){
cin>>a[i].s>>a[i].t;
a[i].id=i; //记录资历
}
sort(a+1,a+n+1,cmp); //按照到达时间从小到大排序
for(int i=1;i<=n;i++){ //遍历每一头牛
if(a[i].s>e){ //第i头牛来的时候，前面吃草的结束了
if(q.empty()){ //队列没有牛等着
e=a[i].s+a[i].t; //更新吃草结束时间
}else{ //队列不为空
int wait=e-q.top().s; //队首的等待时间
ans=max(ans,wait);
e+=q.top().t; //更新吃草结束时间
q.pop(); //队首吃草了，出队
i--; //e比a[i].s大很多，让队列里面的牛先吃，i现在不能入队
}
}else{ //前面的还没有结束，入队等着
q.push(a[i]); //第i头牛入队等着
}
}
while(q.size()){ //队列里面还有牛
int wait=e-q.top().s; //队首的等待时间
ans=max(ans,wait);
e+=q.top().t; //更新吃草结束时间
q.pop(); //队首吃草了，出队
}
cout<<ans;
return 0;
}
/* Problem: 资历
Language: C++ Result: 正确 Time: 2026-10-06 16:23:54
User: admin Problem: 2541 contest_id: 0*/
#include<iostream>
#include<queue>
#include<algorithm>
using namespace std;
int n,ans=0,e=-1;
struct node{
int s,t,id; //s达到时间，t吃草时间，id资历（数字小，资历老）
friend bool operator<(node n1,node n2){
return n1.id>n2.id; //资历数字小的排前面（数字小，资历老）
}
}a[100010];
bool cmp(node n1,node n2){
return n1.s<n2.s; //到达时间小的排前面
}
priority_queue<node> q;
int main(){
cin>>n;
for(int i=1;i<=n;i++){
cin>>a[i].s>>a[i].t;
a[i].id=i; //记录资历
}
sort(a+1,a+n+1,cmp); //按照到达时间从小到大排序
for(int i=1;i<=n;i++){ //遍历每一头牛
if(a[i].s>e){ //第i头牛来的时候，前面吃草的结束了
if(q.empty()){ //队列没有牛等着
e=a[i].s+a[i].t; //更新吃草结束时间
}else{ //队列不为空
int wait=e-q.top().s; //队首的等待时间
ans=max(ans,wait);
e+=q.top().t; //更新吃草结束时间
q.pop(); //队首吃草了，出队
i--; //e比a[i].s大很多，让队列里面的牛先吃，i先等等
}
}else{ //前面的还没有结束，入队等着
q.push(a[i]); //第i头牛入队等着
}
}
while(q.size()){ //队列里面还有牛
int wait=e-q.top().s; //队首的等待时间
ans=max(ans,wait);
e+=q.top().t; //更新吃草结束时间
q.pop(); //队首吃草了，出队
}
cout<<ans;
return 0;
}
/* Problem: 资历
Language: C++ Result: 正确 Time: 2026-10-06 16:22:41
User: admin Problem: 2541 contest_id: 0*/
#include<iostream>
#include<queue>
#include<algorithm>
using namespace std;
int n,ans=0,e=-1;
struct node{
int s,t,id; //s达到时间，t吃草时间，id资历（数字小，资历老）
friend bool operator<(node n1,node n2){
return n1.id>n2.id; //资历数字小的排前面（数字小，资历老）
}
}a[100010];
bool cmp(node n1,node n2){
return n1.s<n2.s; //到达时间小的排前面
}
priority_queue<node> q;
int main(){
cin>>n;
for(int i=1;i<=n;i++){
cin>>a[i].s>>a[i].t;
a[i].id=i; //记录资历
}
sort(a+1,a+n+1,cmp); //按照到达时间从小到大排序
for(int i=1;i<=n;i++){ //遍历每一头牛
if(a[i].s>=e){ //第i头牛来的时候，前面吃草的结束了
if(q.empty()){ //队列没有牛等着
e=a[i].s+a[i].t; //更新吃草结束时间
}else{ //队列不为空
int wait=e-q.top().s; //队首的等待时间
ans=max(ans,wait);
e+=q.top().t; //更新吃草结束时间
q.pop(); //队首吃草了，出队
if(e<a[i].s) i--; //e比a[i].s大很多，让队列里面的牛先吃
else q.push(a[i]); //正好相等的时候才能进来
}
}else{ //前面的还没有结束，入队等着
q.push(a[i]); //第i头牛入队等着
}
}
while(q.size()){ //队列里面还有牛
int wait=e-q.top().s; //队首的等待时间
ans=max(ans,wait);
e+=q.top().t; //更新吃草结束时间
q.pop(); //队首吃草了，出队
}
cout<<ans;
return 0;
}
/* Problem: 资历
Language: C++ Result: 正确 Time: 2026-10-06 16:20:23
User: admin Problem: 2541 contest_id: 0*/
#include<iostream>
#include<queue>
using namespace std;
int n,k,b[1010],ans=0,mx;
int main(){
cin>>n>>k;
for(int i=1;i<=n;i++){
cin>>b[i];
mx=max(mx,b[i]); //某棵树的最大浆果数量
}
for(int i=1;i<=mx;i++){//尝试每个篮子的最大值为i
int cnt=0; //cnt表示装i个的篮子数量
priority_queue<int> q; //默认是大根堆，堆顶就是最大值
for(int j=1;j<=n;j++){ //遍历没棵树
cnt+=b[j]/i;
q.push(b[j]%i); //凑不满i个的余数入堆，万一凑不满k篮，则有用
}
//已经有了cnt篮，每篮i个
if(cnt<k/2) continue; //不够k/2篮，小西只能得到0个浆果
else if(cnt<k){ //需要从余数中凑满k篮
int res=(cnt-k/2)*i;
int t=k-cnt; //还要从余数中凑t篮
while(q.size()&&t--){
res+=q.top();
q.pop();
}
ans=max(ans,res);
}else{//超过k篮，直接取走k/2篮的浆果
ans=max(ans,k/2*i);
}
}
cout<<ans;
return 0;
}
/*
1 尝试每个篮子的最大值依次枚举i：从1~mx(mx表示最多的树的数量)
2 按照策略分配浆果，如果均分的不够，则用少于i个的水果（从大到小）补充剩余篮子
在上述所有的方案里面，取后面K/2个篮子之和的最大值
*/
/* Problem: 采浆果
Language: C++ Result: 正确 Time: 2026-10-06 15:29:35
User: admin Problem: 2552 contest_id: 0*/
#include<iostream>
#include<queue>
#include<algorithm>
using namespace std;
int n,ans=0,mxt=0;
struct node{
int t,v; //t过期时间，v利润
friend bool operator<(node n1,node n2){//友元函数
return n1.v<n2.v;
}
}a[10010];
bool cmp(node n1,node n2){
return n1.t>n2.t; //时间大的排前面
}
priority_queue<node> q; //在优先队列q中默认按照利润从大到小排序
int main(){
cin>>n;
for(int i=1;i<=n;i++){
cin>>a[i].v>>a[i].t;
mxt=max(mxt,a[i].t); //取最晚的过期时间为mxt
}
sort(a+1,a+n+1,cmp); //按时间从后往前排序
for(int i=mxt,k=1;i>=1;i--){ //从最后一天开始尝试卖东西，从后往前
while(a[k].t==i){ //第i天过期的全部入队
q.push(a[k]);
k++;
}
//第i天可以卖一件商品
if(q.size()){ //队列非空
ans+=q.top().v;
q.pop();
}
}
cout<<ans;
return 0;
}
/* Problem: 商店
Language: C++ Result: 正确 Time: 2026-10-06 14:40:19
User: admin Problem: 3935 contest_id: 0*/
#include<iostream>
#include<algorithm>
using namespace std;
int n,ans=0;
struct node{
int l,r;
}a[100010];
bool cmp(node n1,node n2){//按照左端点从小到大排序，如果左端点相同右端点按照从大到小排序
if(n1.l==n2.l) return n1.r>n2.r;
return n1.l<n2.l;
}
int main(){
cin>>n;
for(int i=1;i<=n;i++){
int x,y; cin>>x>>y;
a[i].l=x-y; //计算区间左右端点
a[i].r=x+y;
}
sort(a+1,a+n+1,cmp);
int mx=0; //mx表示右端点的前缀最大值
for(int i=1;i<=n;i++){//从前往后遍历，如果当前山的右端点大于前面所有山的右端点，则答案+1
if(a[i].r>mx){
ans++;
mx=a[i].r; //右端点的前缀最大值
}
}
cout<<ans;
return 0;
}
/*
1 计算每个区间的左右端点 [x-y,x+y]
2 按照左端点从小到大排序，如果左端点相同右端点按照从大到小排序
3 从前往后遍历，如果当前山的右端点大于前面所有山的右端点，则答案+1
*/
/* Problem: 山峰数量
Language: C++ Result: 正确 Time: 2026-10-06 11:50:39
User: admin Problem: 2545 contest_id: 0*/
#include<iostream>
using namespace std;
int n,m,a[210],b[210],ans=0,v[210];
//v[i]表示草地编号i的种草类型
int main(){
cin>>n>>m;
for(int i=1;i<=m;i++) cin>>a[i]>>b[i];
for(int i=1;i<=n;i++){ //从草地1到草地n尝试种草
for(int k=1;k<=4;k++){ //尝试1~4号草
int flag=0; //假设位置i可以种草编号为k
//矛盾：小羊喜欢的另外一块草地已经被种了编号k
for(int j=1;j<=m;j++){ //枚举小羊
if(i==b[j]&&v[a[j]]==k || i==a[j]&&v[b[j]]==k){
flag=1; //确定是矛盾的
break;
}
}
if(!flag){ //不矛盾
v[i]=k; //确定草地i种草编号为k
cout<<k;
break;
}
}
}
return 0;
}
/* Problem: 种草
Language: C++ Result: 正确 Time: 2026-10-06 11:25:35
User: admin Problem: 2535 contest_id: 0*/
#include<iostream>
using namespace std;
long long T,n,a[500010],ans=0;
int main(){
cin>>T;
while(T--){
cin>>n;
ans=1e18;//小西吃到的总和初始值
for(int i=1;i<=n;i++){
cin>>a[i];
a[i]+=a[i-1]; //前缀和
}
//阿木吃掉n/2-1,那么小西吃掉中间的n/2+1
for(int i=1;i+n/2<=n;i++){ //枚举小西吃蛋糕的左端点
int j=i+n/2; //小西吃蛋糕的右端点
ans=min(ans,a[j]-a[i-1]); //取区间和[i,j]的最小值
}
cout<<ans<<" "<<a[n]-ans<<endl;
}
return 0;
}
/* Problem: 分割蛋糕
Language: C++ Result: 正确 Time: 2026-10-06 11:02:02
User: admin Problem: 4243 contest_id: 0*/
#include<iostream>
using namespace std;
int n,a[10010],b[10010],ans[10010],sum=0,v[100010];
//v[i]表示位置i原始值是相等的
int main(){
cin>>n;
for(int i=1;i<=n;i++) cin>>a[i];
for(int i=1;i<=n;i++){
cin>>b[i];
if(a[i]==b[i]) sum++,v[i]=1;//统计原始相等位置的数量，并进行标记
}
for(int k=1;k<=n;k++){ //枚举区间的中心位置
int i=k,cnt=0; //cnt相对变化值
for(int j=i;i>=1&&j<=n;i--,j++){//枚举区间长度为奇数，且中心为k的所有区间[i,j]
if(a[j]!=b[i]&&v[i]) cnt--;
else if(a[j]==b[i]&&!v[i]) cnt++;
if(a[i]!=b[j]&&v[j]) cnt--;
else if(a[i]==b[j]&&!v[j]) cnt++;
ans[sum+cnt]++; //当前区间[i,j]对答案的影响
}
i=k,cnt=0; //cnt相对变化值
for(int j=i+1;i>=1&&j<=n;i--,j++){ //枚举区间长度为偶数，且中心为k和k+1的所有区间[i,j]
if(a[j]!=b[i]&&v[i]) cnt--;
else if(a[j]==b[i]&&!v[i]) cnt++;
if(a[i]!=b[j]&&v[j]) cnt--;
else if(a[i]==b[j]&&!v[j]) cnt++;
ans[sum+cnt]++; //当前区间[i,j]对答案的影响
}
}
for(int i=0;i<=n;i++) cout<<ans[i]<<endl;
return 0;
}
/* Problem: 牛的检查
Language: C++ Result: 正确 Time: 2026-10-06 10:11:33
User: admin Problem: 4473 contest_id: 0*/
#include<iostream>
#include<algorithm>
using namespace std;
int n,t,a[100010],b[100010],ans=0,ta,tb;
int main(){
cin>>n>>t;
for(int i=1;i<=n;i++) cin>>a[i],a[i]+=a[i-1];
for(int i=1;i<=n;i++) cin>>b[i],b[i]+=b[i-1];
for(int i=0;i<=n;i++){ //枚举a选择前i个关卡
if(a[i]>t) break;
int x=t-a[i]; //可以用与b选择关卡的时间
int j=upper_bound(b+1,b+n+1,x)-b-1; //二分找到最后一个<=x的位置：>x的第一个位置-1
ans=max(ans,i+j);
}
cout<<ans;
return 0;
}
/* Problem: 闯关游戏
Language: C++ Result: 正确 Time: 2026-10-05 17:06:22
User: admin Problem: 2007 contest_id: 0*/
#include<iostream>
using namespace std;
int n,a[100010],b[100010],v[100010],ans=0;
//v[i]表示数字i已经被移动过，可以直接过掉
int main(){
cin>>n;
for(int i=1;i<=n;i++) cin>>a[i];
for(int j=1;j<=n;j++) cin>>b[j];
for(int i=1,j=1;i<=n&&j<=n;){
while(v[a[i]]) i++; //数字a[i]已经在前面比较时，处理了
if(a[i]!=b[j]){ //b[j]这个数字需要从a数组的后面某个位置拿过来
v[b[j]]=1; //表示数字b[j]已经被处理过了
ans++; //操作次数+1
j++;
}else{
v[b[j]]=1; //表示数字b[j]已经被处理过了
i++,j++;
}
}
cout<<ans;
return 0;
}
/* Problem: 拍照顺序
Language: C++ Result: 正确 Time: 2026-10-05 16:15:34
User: admin Problem: 2523 contest_id: 0*/
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
long long n,q,ans=0;
string s;
vector<long long> v[300]; //v[i]用于保存字符i的所有下标位置
int main(){
cin>>n>>q>>s;
for(int i=0;i<s.size();i++) v[s[i]].push_back(i+1); //存储字符s[i]的位置i
while(q--){ //q次询问
int l,r; scanf("%d %d",&l,&r);
ans=-1; //答案初始值为-1,表示不存在这样的三角形
for(int c1='a';c1<='z';c1++){ //枚举abb中的第一个字符
int i=lower_bound(v[c1].begin(),v[c1].end(),l)-v[c1].begin(); //区间[l,r]中第一个字符c1的位置
if(i>=v[c1].size()) continue; //c1在区间[l,r]中无法构成有效的abb三角形
for(int c3='a';c3<='z';c3++){ //枚举abb中的第三个字符
if(c3==c1 || v[c3].size()<2) continue; //无法构成有效的abb三角形
int k=upper_bound(v[c3].begin(),v[c3].end(),r)-v[c3].begin()-1;
if(k<=0 || v[c3][k-1]<=v[c1][i]) continue; //无法构成有效的abb三角形
int j=upper_bound(v[c3].begin(),v[c3].end(),(v[c3][k]+v[c1][i])/2)-v[c3].begin();
if(j<k&&j>=0&&v[c1][i]<v[c3][j]) ans=max(ans,(v[c3][k]-v[c3][j])*(v[c3][j]-v[c1][i]));
j--;
if(j<k&&j>=0&&v[c1][i]<v[c3][j]) ans=max(ans,(v[c3][k]-v[c3][j])*(v[c3][j]-v[c1][i]));
}
}
printf("%lld\n",ans);
}
return 0;
}
/* Problem: 三元组
Language: C++ Result: 正确 Time: 2026-10-05 15:40:39
User: admin Problem: 4479 contest_id: 0*/
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
long long n,q,ans=0;
string s;
vector<long long> v[300]; //v[i]用于保存字符i的所有下标位置
int main(){
cin>>n>>q>>s;
for(int i=0;i<s.size();i++) v[s[i]].push_back(i); //存储字符s[i]的位置i
while(q--){ //q次询问
int l,r; scanf("%d %d",&l,&r);
l--;r--; //字符下标从0开始
ans=-1; //答案初始值为-1,表示不存在这样的三角形
for(int c1='a';c1<='z';c1++){ //枚举abb中的第一个字符
int i=lower_bound(v[c1].begin(),v[c1].end(),l)-v[c1].begin(); //区间[l,r]中第一个字符c1的位置
if(i>=v[c1].size()) continue; //c1在区间[l,r]中无法构成有效的abb三角形
for(int c3='a';c3<='z';c3++){ //枚举abb中的第三个字符
if(c3==c1 || v[c3].size()<2) continue; //无法构成有效的abb三角形
int k=upper_bound(v[c3].begin(),v[c3].end(),r)-v[c3].begin()-1;
if(k<=0 || v[c3][k-1]<=v[c1][i]) continue; //无法构成有效的abb三角形
int j=upper_bound(v[c3].begin(),v[c3].end(),(v[c3][k]+v[c1][i])/2)-v[c3].begin();
if(j<k) ans=max(ans,(v[c3][k]-v[c3][j])*(v[c3][j]-v[c1][i]));
j--;
if(j>=0&&v[c1][i]<v[c3][j]) ans=max(ans,(v[c3][k]-v[c3][j])*(v[c3][j]-v[c1][i]));
}
}
printf("%lld\n",ans);
}
return 0;
}
/* Problem: 三元组
Language: C++ Result: 正确 Time: 2026-10-05 15:28:57
User: admin Problem: 4479 contest_id: 0*/
#include<iostream>
using namespace std;
long long n,m,ans=0,f[1000010],s[1000010],mn=1e9,mx=0;
bool check(int x){//判断是否可以找到至少一个连续区间的最大辣度是x，且风味和>=m
long long sum=0; //风味和初始为0
for(int i=1;i<=n;i++){
if(s[i]>x) sum=0; //区间断了，重新开始
else sum+=f[i]; //区间连续
if(sum>=m) return true; //找了一个满足条件的区间，结束了
}
return false; //循环结束，都没有找到这样的区间
}
int main(){
cin>>n>>m;
for(int i=1;i<=n;i++){
cin>>f[i]>>s[i];
mn=min(mn,s[i]);
mx=max(mx,s[i]);
}
int l=mn,r=mx;
while(l<=r){
int mid=(l+r)/2;
if(check(mid)) ans=mid,r=mid-1; //答案有可能更小
else l=mid+1; //答案只可能更大
}
cout<<ans;
return 0;
}
/*
1 辣度最小值满足单调性，所以可以二分
2 当辣度最大值为mid时，只需要从前往后找到一个连续区间的风味和>=m，且辣度最大值不超过mid即可
*/
/* Problem: 辣度
Language: C++ Result: 正确 Time: 2026-10-05 14:30:40
User: admin Problem: 4800 contest_id: 0*/
#include<iostream>
#include<algorithm>
using namespace std;
int n,m,c,a[100010],ans=0;
bool check(int x){ //检查最长等待时间x是否可以拉走所有的牛
int cnt=1,s=1; //第1头牛肯定需要第1辆车，s表示当前这辆车等待最长的牛的编号
for(int i=1;i<=n;i++){ //遍历每一头牛的到机场时间
if(a[i]-a[s]>x || i-s+1>c){ //第s头牛等待时间不能超过x，且s~i这个区间的牛数不能超过容量c
cnt++; //新开一趟车
s=i; //这头牛成了新车的等待时间最长的牛
}
}
return cnt<=m; //m辆车够则返回true
}
int main(){
cin>>n>>m>>c;
for(int i=1;i<=n;i++) cin>>a[i];
sort(a+1,a+n+1);
int l=0,r=a[n]-a[1]; //答案所在的区间是l-r
while(l<=r){
int mid=(l+r)/2; //检查最长等待时间mid是否可行
if(check(mid)) ans=mid,r=mid-1; //等待时间有可能更短
else l=mid+1; //等待时间只可能更长
}
cout<<ans;
return 0;
}
/* Problem: 牛吃草大会
Language: C++ Result: 正确 Time: 2026-10-05 11:54:29
User: admin Problem: 2540 contest_id: 0*/
#include<iostream>
#include<algorithm>
using namespace std;
long long n,k,L,a[100010],ans=0;
bool cmp(long long x,long long y){
return x>y;
}
bool check(int x){ //检查指数x是否可行
long long s=0; //统计作弊的引用总次数
for(int i=1;i<=x;i++){ //达到x篇就够了
if(a[i]<x){
if(x-a[i]>k) return false;
s+=x-a[i];
}
if(s>k*L) return false;
}
return true; //已经有x篇的引用次数达到x以上
}
int main(){
cin>>n>>k>>L;
for(int i=1;i<=n;i++) cin>>a[i];
sort(a+1,a+n+1,cmp); //引用次数从大到小排序
int l=0,r=n;
while(l<=r){
int mid=(l+r)/2;
if(check(mid)) ans=mid,l=mid+1;
else r=mid-1;
}
cout<<ans;
return 0;
}
/* Problem: 最大 h 指数
Language: C++ Result: 正确 Time: 2026-10-05 10:51:16
User: admin Problem: 2572 contest_id: 0*/
#include<iostream>
#include<algorithm>
using namespace std;
int n,c,a[100010],ans=0;
bool check(int x){ //检查两头牛之间的最小距离是x，是否可行
int s=a[1],cnt=1; //s表示已经安排宿舍的最后一头牛的位置，cnt表示安排了宿舍的牛数
for(int i=2;i<=n;i++){
if(a[i]-s>=x){
cnt++; //又有一头牛有了宿舍
s=a[i]; //s表示已经安排宿舍的最后一头牛的位置
if(cnt>=c) return true;
}
}
return false; //所有牛栏安排完毕，但是不够c头牛分配
}
int main(){
cin>>n>>c;
for(int i=1;i<=n;i++) cin>>a[i];
sort(a+1,a+n+1); //找牛栏位置从小到大排序
int l=0,r=a[n]-a[1];
while(l<=r){
int mid=(l+r)/2;
if(check(mid)) ans=mid,l=mid+1; //答案有可能更大
else r=mid-1;
}
cout<<ans;
return 0;
}
/* Problem: 愤怒的牛
Language: C++ Result: 正确 Time: 2026-10-05 10:06:18
User: admin Problem: 2117 contest_id: 0*/
#include<iostream>
#include<algorithm>
using namespace std;
int n,m,ans=0;
struct node{
int p,a; //p单价，a数量
}a[100010];
bool cmp(node n1,node n2){
return n1.p<n2.p;
}
int main(){
cin>>n>>m;
for(int i=1;i<=m;i++) cin>>a[i].p>>a[i].a;
sort(a+1,a+m+1,cmp);
for(int i=1;i<=m;i++){
if(n>=a[i].a){
n-=a[i].a;
ans+=a[i].a*a[i].p; //把这个农户的全买
}else{
ans+=n*a[i].p; //剩余的n全部在这个农户这里买完
n=0;
break;
}
}
cout<<ans;
return 0;
}
/* Problem: 混合牛奶
Language: C++ Result: 正确 Time: 2026-10-05 09:48:39
User: admin Problem: 1570 contest_id: 0*/
#include <iostream>
#include <algorithm>
using namespace std;
int n, m, ans;
struct node{//存奶农结构体
int p, a;
}a[100010];
int cmp(node a,node b){ //重载排序
return a.p<b.p; //价格低的排前面
}
int main(){
cin >> n >> m;
for(int i = 1; i <= m;i++) cin >> a[i].p >> a[i].a;
sort(a+1,a+1+m,cmp);
for (int i = 1; i <= m;i++){ //贪心
if(n>=a[i].a){ //当前的钱够买所有的奶
n-=a[i].a;
ans+=a[i].a*a[i].p; //全买掉
}else{//不够买所有的奶
ans+=n*a[i].p; //能买多少买多少并结束
n=0;
break;
}
}
cout << ans;
return 0;
}
/* Problem: 混合牛奶
Language: C++ Result: 正确 Time: 2026-09-24 16:44:45
User: admin Problem: 1570 contest_id: 0*/
#include<iostream>
#include<algorithm>
using namespace std;
int n,c,a[100010],ans=0;
bool check(int x){ //检查最小x的距离，是否可以住下c头牛
int s=a[1],cnt=1; //cnt表示可以住下的牛的数量
for(int i=2;i<=n;i++) {
if(a[i]-s>=x){//距离达到x
cnt++;//又有一头牛可以住下来
s=a[i];//更新最后一头牛的位置
if(cnt>=c) return true; //已经够住下c头牛
}
}
return false;//住不下
}
int main() {
scanf("%d%d",&n,&c);
for(int i=1;i<=n;i++) scanf("%d",&a[i]);
sort(a+1,a+n+1);
int l=0,r=a[n]-a[1];
while(l<=r) {
int mid=(l+r)/2;
if(check(mid)) ans=mid,l=mid+1;//答案有可能更大
else r=mid-1;//答案只可能更小
}
printf("%d",ans);
return 0;
}
/* Problem: 愤怒的牛
Language: C++ Result: 正确 Time: 2026-09-24 16:09:21
User: admin Problem: 2117 contest_id: 0*/
#include<iostream>
using namespace std;
typedef long long ll;
long long n,ans=0,a[15005],b[15005],sum,c[15005],p[15005];
//ans表示初始相等位置的数量，p[i]=1表示位置i的ai和bi相同
int main(){
cin>>n;
for(int i=1;i<=n;i++) cin>>a[i];//输入A数组
for(int j=1;j<=n;j++){
cin>>b[j]; //输入b数组
if(a[j]==b[j]) ans++,p[j]=1;//预处理ans，打位置标记（后面会用到）
}
for(int k=1;k<=n;k++){ //以k为中心枚举
int i=k; //用i记作k，因为k不能改动
int sum=0; //记录相较于原来答案的变化
for(int j=i;i>0&&j<=n;j++,i--){//区间内，数的个数为奇数
if(a[j]!=b[i]&&p[i]) sum--;//如果下标为i,j的两个数字调换后不一样且 调换前一样（P数组判断）会比原先少一个
else if(a[j]==b[i]&&!p[i]) sum++;//如果下标为i,j的两个数字调换后一样且 调换前不一样（P数组判断）会比原先多一个
if(a[i]!=b[j]&&p[j]) sum--;
else if(a[i]==b[j]&&!p[j]) sum++;//反之同理
c[ans+sum]++; //得到的答案数++
}
sum=0;//i和sum都变了，所以要重新赋初值
i=k;
for(int j=i+1;i>0&&j<=n;j++,i--){//区间内，数的个数为偶数，for循环里面相同
if(a[j]!=b[i]&&p[i]) sum--;
else if(a[j]==b[i]&&!p[i]) sum++;
if(a[i]!=b[j]&&p[j]) sum--;
else if(a[i]==b[j]&&!p[j]) sum++;
c[ans+sum]++; //原始加上变化的，得到的答案++
}
}
for(int i=0;i<=n;i++)cout<<c[i]<<endl;//从小到大输出答案
return 0;
}
/* Problem: 牛的检查
Language: C++ Result: 正确 Time: 2026-09-21 15:00:19
User: admin Problem: 4473 contest_id: 0*/
#include<iostream>
using namespace std;
typedef long long ll;
ll t,n,a[500005],ans;
int main() {
cin>>t;
while(t--){
cin>>n;
ans=1e18; //初始化位极大值
for(int i=1;i<=n;++i){
cin>>a[i];
a[i]+=a[i-1]; //前缀和
}
int ln=n/2;
for(int i=1;i+n/2<=n;++i) //合并区间是i~i+n/2
ans=min(ans,a[i+n/2]-a[i-1]);
cout<<ans<<" "<<a[n]-ans<<endl;
}
return 0;
}
/* Problem: 分割蛋糕
Language: C++ Result: 正确 Time: 2026-09-21 08:39:57
User: admin Problem: 4243 contest_id: 0*/
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
long long n,q,ans;
string s;
vector<long long> v[300];//c[i]存储所有字符i的所有下标位置
int main(){
cin>>n>>q>>s;
for(int i=0;i<n;i++) v[s[i]].push_back(i); //存储每个s[i]的下标位置
while(q--){
int l,r; scanf("%d %d",&l,&r); //查询区间
l--;r--; ans=-1;
for(int c1='a';c1<='z';c1++){ //枚举ABB中的第一个字符A
int i=lower_bound(v[c1].begin(),v[c1].end(),l)-v[c1].begin();
if(i>=v[c1].size() || i>=r-1) continue; //不在区间范围内
for(int c3='a';c3<='z';c3++){//枚举ABB中的第三个字符B
if(c3==c1 || v[c3].size()<2) continue; //c3==c1 或 c3不够2个
int k=upper_bound(v[c3].begin(),v[c3].end(),r)-v[c3].begin()-1;
if(k<=0 || v[c3][k-1]<=v[c1][i]) continue; //不能构成ABB
//第一个 ＞v[c3][k]+v[c1][i])/2 的位置，即ABB中的第二个字符B的最佳位置
int j=upper_bound(v[c3].begin(),v[c3].end(),(v[c3][k]+v[c1][i])/2)-v[c3].begin();
if(j<k) ans=max(ans,(v[c3][k]-v[c3][j])*(v[c3][j]-v[c1][i]));
j--;//第一个 ≤v[c3][k]+v[c1][i])/2 的位置，也有可能是ABB中的第二个字符B的最佳位置
if(j>=0&&v[c1][i]<v[c3][j]) ans=max(ans,(v[c3][k]-v[c3][j])*(v[c3][j]-v[c1][i]));
}
}
printf("%lld\n",ans);
}
return 0;
}
/* Problem: 三元组
Language: C++ Result: 正确 Time: 2026-09-20 19:00:48
User: admin Problem: 4479 contest_id: 0*/
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
long long n,q,ans;
string s;
vector<long long> v[300];//c[i]存储所有字符i的所有下标位置
int main(){
cin>>n>>q>>s;
for(int i=0;i<n;i++) v[s[i]].push_back(i); //存储每个s[i]的下标位置
while(q--){
int l,r; cin>>l>>r; //查询区间
l--;r--; ans=-1;
for(int c1='a';c1<='z';c1++){ //枚举ABB中的第一个字符A
int i=lower_bound(v[c1].begin(),v[c1].end(),l)-v[c1].begin();
if(i>=v[c1].size() || i>=r-1) continue; //不在区间范围内
for(int c3='a';c3<='z';c3++){//枚举ABB中的第三个字符B
if(c3==c1 || v[c3].size()<2) continue; //c3==c1 或 c3不够2个
int k=upper_bound(v[c3].begin(),v[c3].end(),r)-v[c3].begin()-1;
if(k<=0 || v[c3][k-1]<=v[c1][i]) continue; //不能构成ABB
//第一个 ＞v[c3][k]+v[c1][i])/2 的位置，即ABB中的第二个字符B的最佳位置
int j=upper_bound(v[c3].begin(),v[c3].end(),(v[c3][k]+v[c1][i])/2)-v[c3].begin();
if(j<k) ans=max(ans,(v[c3][k]-v[c3][j])*(v[c3][j]-v[c1][i]));
j--;//第一个 ≤v[c3][k]+v[c1][i])/2 的位置，也有可能是ABB中的第二个字符B的最佳位置
if(j>=0&&v[c1][i]<v[c3][j]) ans=max(ans,(v[c3][k]-v[c3][j])*(v[c3][j]-v[c1][i]));
}
}
cout<<ans<<'\n';
}
return 0;
}
/* Problem: 三元组
Language: C++ Result: 正确 Time: 2026-09-20 18:58:43
User: admin Problem: 4479 contest_id: 0*/
#include<iostream> //递推方法2：从下往上推
using namespace std;//f[i][j]表示从最后一行走到a[i][j]的最大值
int n,a[1010][1010],f[1010][1010],ans=0;
int main(){
cin>>n;
for(int i=1;i<=n;i++)
for(int j=1;j<=i;j++) cin>>a[i][j];
for(int j=1;j<=n;j++) f[n][j]=a[n][j]; //初始值
for(int i=n-1;i>=1;i--){ //从下往上推
for(int j=1;j<=i;j++){
f[i][j]=max(f[i+1][j],f[i+1][j+1])+a[i][j]; //递推关系
}
}
cout<<f[1][1]; //答案：从最后一行走到a[1][1]的最大值
return 0;
}
/* Problem: 数字三角形
Language: C++ Result: 正确 Time: 2026-09-19 15:56:54
User: admin Problem: 1302 contest_id: 0*/
#include<iostream> //递推方法1：从上往下推
using namespace std;//f[i][j]表示从a[1][1]走到a[i][j]的最大和
int n,a[1010][1010],f[1010][1010],ans=0;
int main(){
cin>>n;
for(int i=1;i<=n;i++)
for(int j=1;j<=i;j++) cin>>a[i][j];
f[1][1]=a[1][1]; //初始值
for(int i=2;i<=n;i++){
for(int j=1;j<=i;j++){
f[i][j]=max(f[i-1][j],f[i-1][j-1])+a[i][j];//递推
}
}
for(int j=1;j<=n;j++) ans=max(ans,f[n][j]); //答案在f[n]
cout<<ans;
return 0;
}
/* Problem: 数字三角形
Language: C++ Result: 正确 Time: 2026-09-19 15:48:28
User: admin Problem: 1302 contest_id: 0*/
#include<iostream>
using namespace std;
int n,a[100100],ans=0,mx;//mx表示前缀最大值
int main(){
cin>>n>>a[1];
ans+=a[1]; //第1项的最大值就是a[1]
mx=a[1]; //第1项的最大值就是a[1]
for(int i=2;i<=n;i++){
a[i]=(379*a[i-1]+131)%997; //递推：计算数列
mx=max(mx,a[i]); //计算前缀最大值
ans+=mx;
}
cout<<ans;
return 0;
}
/* Problem: 前缀最大值
Language: C++ Result: 正确 Time: 2026-09-19 15:18:04
User: admin Problem: 2687 contest_id: 0*/
#include<iostream>
using namespace std;
int n,ans=0,a[100010];
int main(){
a[1]=2; //1刀切成2份
cin>>n;
for(int i=2;i<=n;i++){
a[i]=a[i-1]+i; //递推关系式：从已知推未知
}
cout<<a[n];
return 0;
}
/* Problem: 切蛋糕
Language: C++ Result: 正确 Time: 2026-09-19 15:12:48
User: admin Problem: 1977 contest_id: 0*/
#include<iostream>
using namespace std;
int r,c,k,ans=0;
char a[110][110];
bool f(int x,int y){//从坐标x,y往右，正好是连续的k个.
for(int j=y;j<=y+k-1;j++){ //往右边遍历k个位置
if(a[x][j]!='.') return false;
}
return true;
}
bool g(int x,int y){//从坐标x,y往下，正好是连续的k个.
for(int i=x;i<=x+k-1;i++){ //往下边遍历k个位置
if(a[i][y]!='.') return false;
}
return true;
}
int main(){
cin>>r>>c>>k;
for(int i=1;i<=r;i++){
for(int j=1;j<=c;j++){
cin>>a[i][j]; //输入地图
}
}
for(int i=1;i<=r;i++){
for(int j=1;j<=c;j++){ //枚举队伍的起点a[i][j]
if(a[i][j]=='.'){ //a[i][j]必须是空地，才能作为起点
if(f(i,j)) ans++; //往右数，正好是连续的k个.
if(g(i,j)) ans++; //往下数，正好是续的k个.
}
}
}
if(k>1) cout<<ans;
else cout<<ans/2; //k==1特殊情况，不存在往右边和往下面两种情况
return 0;
}
/* Problem: 舞台列队
Language: C++ Result: 正确 Time: 2026-09-19 14:48:50
User: admin Problem: 2345 contest_id: 0*/
#include<iostream>
using namespace std;
int n,ans=0,a[300][300];
int main(){
cin>>n;
for(int i=1;i<=n;i++){
int x,y;
cin>>x>>y;
a[x+110][y+110]=1; //数组下标计数，坐标有负数则统一偏移100
}
for(int i=0;i<=220;i++){
for(int j=0;j<=220;j++){ //枚举a[i][j]作为左上角的坐标点
if(a[i][j]){ //左上角a[i][j]有标记
for(int k=i+1;k<=220;k++){ //枚举左下角的点
if(a[k][j]){ //左下角a[k][j]有标记
for(int g=j+1;g<=220;g++){ //枚举右边的那条边
if(a[i][g] && a[k][g]){ //右上角和右下角有标记
ans++;
//cout<<i<<' '<<j<<';'<<k<<' '<<g<<endl;
}
}
}
}
}
}
}
cout<<ans;
return 0;
}
/* Problem: 统计数量
Language: C++ Result: 正确 Time: 2026-09-19 14:26:39
User: admin Problem: 2422 contest_id: 0*/
#include<iostream>
#include<cstring>
using namespace std;
char a[1010];
int main(){
cin>>a;
int len=strlen(a); //计算出字符串a的实际长度
for(int i=len-2;i>=0;i--){ //#不需要输出
cout<<a[i];
}
return 0;
}
/* Problem: 字符串倒序输出
Language: C++ Result: 正确 Time: 2026-09-19 11:18:43
User: admin Problem: 1130 contest_id: 0*/
#include<iostream>
using namespace std;
char c1[1010]="Hello Hi"; //默认：数据的下标是从0开始的
char c2[1010]="Nice to Meet You";
int main(){
cout<<c1<<endl<<c2<<endl;
cout<<c1[1]<<c1[3]<<c1[5]<<c1[7]<<endl;
cout<<c2[0]<<c2[2]<<c2[4]<<c2[6]<<c2[8]<<endl;
return 0;
}
/* Problem: 字符数组的定义赋值与输出
Language: C++ Result: 正确 Time: 2026-09-19 11:00:45
User: admin Problem: 1127 contest_id: 0*/
#include<iostream>
#include<cmath>
using namespace std;
bool check(int x){ //函数功能：判断x是完全数
int cnt=1; //1肯定是x的因子
for(int i=2;i<=sqrt(x);i++){ //所有小于x的因子全部累加起来
if(x%i==0){
cnt+=i; //x的因子累加
cnt+=x/i; //因子是成对的
if(i*i==x) cnt-=i; //x正好是完全平方数，那么就多加了一个i
}
}
return cnt==x; //除x之外的因子之和 正好等于 x，则x是完全数
}
int n;
int main(){
cin>>n;
for(int i=2;i<=n;i++){//枚举2~n之间的每个数字
if(check(i)){ //判断i是完全数
cout<<i<<" ";
}
}
return 0;
}
/* Problem: 完全数
Language: C++ Result: 正确 Time: 2026-09-19 10:35:18
User: admin Problem: 1164 contest_id: 0*/
#include<iostream>
#include<cmath>
using namespace std;
int a,b;
bool prime(int x){ //功能：判断x是否是质数
for(int i=2;i<=sqrt(x);i++){ //i*i<=x 等价于 i<=sqrt(x)
if(x%i==0){ //找到了一个因子（不是1，也不是自身）
return false;
}
}
return true;
}
int main(){
cin>>a>>b;
for(int i=a;i<=b;i++){ //计算a~b之间，每一个数字i的最大质因子
for(int j=i;;j--){//计算i的最大质因子：从大到小枚举i的因子
if(i%j==0&&prime(j)){//j是i的因子，且j是质数，那么j就是i的最大质因子
cout<<j;
if(i<b) cout<<','; //只有最后一个数字b后面没有逗号
break; //break只能跳出当前层循环
}
}
}
return 0;
}
/* Problem: 最大质因子(2)
Language: C++ Result: 正确 Time: 2026-09-19 10:18:56
User: admin Problem: 1680 contest_id: 0*/
#include<iostream>
#include<cmath>
using namespace std;
int n,ans=0;
bool prime(int x){ //功能：判断x是否是质数
for(int i=2;i<=sqrt(x);i++){ //i*i<=x 等价于 i<=sqrt(x)
if(x%i==0){ //找到了一个因子（不是1，也不是自身）
return false;
}
}
return true;
}
int main(){
cin>>n;
for(int i=2;i<=n/2;i++){ //枚举较小的那个加数 i
int j=n-i; //计算出较大的另一个加数 j
if(prime(i)&&prime(j)){ //i和j都是质数
ans=max(ans,i*j); //取乘积的最大值
}
}
cout<<ans;
return 0;
}
/* Problem: 质数的和与积
Language: C++ Result: 正确 Time: 2026-09-19 10:07:35
User: admin Problem: 1677 contest_id: 0*/
#include<iostream>
#include<cmath>
using namespace std;
int n,ans=0;
bool prime(int x){ //功能：判断x是否是质数
for(int i=2;i<=sqrt(x);i++){ //i*i<=x 等价于 i<=sqrt(x)
if(x%i==0){ //找到了一个因子（不是1，也不是自身）
return false;
}
}
return true;
}
int main(){
cin>>n;
for(int i=n;;i--){ //从大到小 枚举n的因子
if(n%i==0&&prime(i)){ //i是n的因子，且i是质数，那么i就是n的最大质因子
cout<<i;
break;
}
}
return 0;
}
/* Problem: 最大质因子
Language: C++ Result: 正确 Time: 2026-09-19 09:56:02
User: admin Problem: 2298 contest_id: 0*/
#include<iostream>
#include<cmath>
using namespace std;
int n,ans=0;
bool prime(int x){ //功能：判断x是否是质数
for(int i=2;i<=sqrt(x);i++){ //i*i<=x 等价于 i<=sqrt(x)
if(x%i==0){ //找到了一个因子（不是1，也不是自身）
return false;
}
}
return true;
}
int main(){
cin>>n;
for(int i=n;;i--){
if(prime(i)){ //判断i是质数
cout<<i;
return 0;
}
}
return 0;
}
/* Problem: 比n小的最大质数
Language: C++ Result: 正确 Time: 2026-09-19 09:45:34
User: admin Problem: 1153 contest_id: 0*/
#include<iostream>
using namespace std;
long long n,ans=0; //注意题目的数据范围
int main(){
cin>>n;
while(n>0){
int g=n%10; //把n的个位拆出来
ans+=g*g*g; //连乘3次并累加起来
n/=10; //抹掉n的个位
}
cout<<ans;
return 0;
}
/*
重复做什么？
1、把n的个位拆出来，然后连乘3次并累加起来。
2、抹掉n的个位。
*/
/* Problem: 水仙花指数
Language: C++ Result: 正确 Time: 2026-09-18 19:48:43
User: admin Problem: 1174 contest_id: 0*/
#include<iostream>
using namespace std;
int m,n,ans=0;
int main(){
cin>>m>>n;
for(int i=1;i<=n;i++){ //重复n次
int x;
cin>>x; //第i个人来了，告诉你取药的数量是x
if(m>=x){ //够：给他，更新剩余数量
m-=x;
}else{ //不够：不给他，记录拿不到药品的人数
ans++; //计数
}
}
cout<<ans;
return 0;
}
/*
重复动作：判断药品剩余的数量是否满足当前这个人的需求
够：给他，更新剩余数量
不够：不给他，记录拿不到药品的人数
*/
/* Problem: 药房管理
Language: C++ Result: 正确 Time: 2026-09-18 19:23:04
User: admin Problem: 1626 contest_id: 0*/
#include<iostream>
using namespace std;
int n,ans=0;
int main(){
cin>>n;
if(n<0){ //如果n是负数
cout<<"-";
n=-n; //负负得正
}
//1 取出n的个位，将个位拼接到新数字的最后面
//2 抹掉n的个位
//如果n>0，继续第1步-第2步
while(n>0){
ans=ans*10+n%10; //ans代表新数字，ans扩大10倍+n的个位
n/=10;
}
cout<<ans;
return 0;
}
/* Problem: 数字反转.
Language: C++ Result: 正确 Time: 2026-09-18 19:01:17
User: admin Problem: 1475 contest_id: 0*/
#include<iostream>
using namespace std;
string s1,s2;
int main(){
cin>>s1>>s2;
int p1=s1.find(s2); //查找函数
int p2=s2.find(s1);
if(p1!=-1){//找不到，则查找结果是-1
cout<<s2<<" is substring of "<<s1;
}else if(p2!=-1){
cout<<s1<<" is substring of "<<s2;
}else{
cout<<"No substring";
}
return 0;
}
/* Problem: 验证子串
Language: C++ Result: 正确 Time: 2026-09-18 15:24:55
User: admin Problem: 1660 contest_id: 0*/
#include<iostream>
using namespace std;
string s;
char c;
int main(){
cin>>s>>c;
while(s.find(c)!=-1){
int p=s.find(c); //找到字符c的位置
s.erase(p,1);
}
cout<<s;
return 0;
}
/*
从字符串s中找到所有的字符c，并删除
*/
/* Problem: 删除指定字符
Language: C++ Result: 正确 Time: 2026-09-18 15:20:14
User: admin Problem: 1876 contest_id: 0*/
#include <iostream> //二分的模板2： l<=r
#include <algorithm>
using namespace std;
int n,m,c,a[100005],ans;
int main(){
scanf("%d%d%d",&n,&m,&c);
for(int i=1;i<=n;i++) scanf("%d",&a[i]);
sort(a+1,a+n+1); //到达时间从小到大排序
int l=0,r=a[n]-a[1]; //r是可能的最长等待时间，即第1头牛等到最后1头牛到来
while(l<=r){
int mid=(l+r)>>1,cnt=1,s=1; //cnt表示车辆的数量，s表示等第cnt辆车的最早的牛编号
for(int i=1;i<=n;i++)
if(a[i]-a[s]>mid || i-s+1>c){//等待时间超过mid或当前车辆已满
cnt++; //重新发一辆车
s=i; //等待新车的最早的牛编号
}
if(cnt<=m) ans=mid,r=mid-1; //车辆数充足，则等待时间可以更小
else l=mid+1; //车辆数不足，则等待时间需要更长
}
printf("%d\n",ans);
return 0;
}
/* Problem: 牛吃草大会
Language: C++ Result: 正确 Time: 2026-09-17 13:25:00
User: admin Problem: 2540 contest_id: 0*/
#include <iostream> //二分的模板1： l<r
#include <algorithm>
using namespace std;
int n,m,c,a[100005];
int main(){
scanf("%d%d%d",&n,&m,&c);
for(int i=1;i<=n;i++) scanf("%d",&a[i]);
sort(a+1,a+n+1); //到达时间从小到大排序
int l=0,r=a[n]-a[1]; //r是可能的最长等待时间，即第1头牛等到最后1头牛到来
while(l<r){
int mid=(l+r)>>1,cnt=1,s=1; //cnt表示车辆的数量，s表示等第cnt辆车的最早的牛编号
for(int i=1;i<=n;i++)
if(a[i]-a[s]>mid || i-s+1>c){//等待时间超过mid或当前车辆已满
cnt++; //重新发一辆车
s=i; //等待新车的最早的牛编号
}
if(cnt<=m) r=mid; //车辆数充足，则等待时间可以更小
else l=mid+1; //车辆数不足，则等待时间需要更长
}
printf("%d\n",l);
return 0;
}
/* Problem: 牛吃草大会
Language: C++ Result: 正确 Time: 2026-09-17 13:22:42
User: admin Problem: 2540 contest_id: 0*/
#include<iostream>
using namespace std;
int t,m,b[1010],n[1010];
int fb[1010],fn[1010];
//fb[i]第i个月在北京办公的最大收益，fn[i]第i个月在南京办公的最大收益
int main(){
cin>>t>>m;
for(int i=1;i<=t;i++) cin>>b[i]>>n[i];
//初始值
fb[1]=b[1];
fn[1]=n[1];
for(int i=2;i<=t;i++){ //状态转移
fb[i]=max(fb[i-1]+b[i],fn[i-1]+b[i]-m); //上个月有两种情况：北京、南京
fn[i]=max(fb[i-1]+n[i]-m,fn[i-1]+n[i]); //上个月有两种情况：北京、南京
}
cout<<max(fb[t],fn[t]); //答案
return 0;
}
/* Problem: 移动办公营业额
Language: C++ Result: 正确 Time: 2026-09-12 20:39:27
User: admin Problem: 2401 contest_id: 0*/
#include<iostream>
#include<cstring>
using namespace std;
int ans=0,a,b,c;
int main(){
cin>>a>>b>>c;
for(int i=123;i<=987;i++){
if(i%10==i/10%10 || i%10==i/100 || i/10%10==i/100) continue;//个 十 百位不能相同
if(i%10==0 || i/10%10==0 || i/100==0) continue;//个 十 百位不能为0
for(int j=123;j<=987;j++){
if(j%10==j/10%10 || j%10==j/100 || j/10%10==j/100) continue;//个 十 百位不能相同
if(j%10==0 || j/10%10==0 || j/100==0) continue;//个 十 百位不能为0
if(i%10==j%10 || i%10==j/10%10 || i%10==j/100) continue;//i的个位 不能和 j的个十百位相同
if(i/10%10==j%10 || i/10%10==j/10%10 || i/10%10==j/100) continue;//i的十位 不能和 j的个十百位相同
if(i/100%10==j%10 || i/100%10==j/10%10 || i/100%10==j/100) continue;//i的百位 不能和 j的个十百位相同
for(int k=123;k<=987;k++){
if(k%10==k/10%10 || k%10==k/100 || k/10%10==k/100) continue;//个 十 百位不能相同
if(k%10==0 || k/10%10==0 || k/100==0) continue;//个 十 百位不能为0
if(i%10==k%10 || i%10==k/10%10 || i%10==k/100) continue;//i的个位 不能和 k的个十百位相同
if(i/10%10==k%10 || i/10%10==k/10%10 || i/10%10==k/100) continue;//i的十位 不能和 k的个十百位相同
if(i/100%10==k%10 || i/100%10==k/10%10 || i/100%10==k/100) continue;//i的百位 不能和 k的个十百位相同
if(j%10==k%10 || j%10==k/10%10 || j%10==k/100) continue;//j的个位 不能和 k的个十百位相同
if(j/10%10==k%10 || j/10%10==k/10%10 || j/10%10==k/100) continue;//j的十位 不能和 k的个十百位相同
if(j/100%10==k%10 || j/100%10==k/10%10 || j/100%10==k/100) continue;//j的百位 不能和 k的个十百位相同
if(i*b==j*a && i*c==k*a && j*c==k*b){
cout<<i<<" "<<j<<" "<<k<<endl;
ans++; //方案数+1
}
}
}
}
if(ans==0) cout<<"No!!!";
return 0;
}
/* Problem: 组成三位数（加强）
Language: C++ Result: 正确 Time: 2026-09-12 15:59:39
User: admin Problem: 2343 contest_id: 0*/
#include<iostream>
#include<cstring>
using namespace std;
int ans=0,a,b,c;
int main(){
cin>>a>>b>>c;
for(int i=123;i<=987;i++){
if(i%10==i/10%10 || i%10==i/100 || i/10%10==i/100) continue;//个 十 百位不能相同
if(i%10==0 || i/10%10==0 || i/100==0) continue;//个 十 百位不能为0
for(int j=123;j<=987;j++){
if(j%10==j/10%10 || j%10==j/100 || j/10%10==j/100) continue;//个 十 百位不能相同
if(j%10==0 || j/10%10==0 || j/100==0) continue;//个 十 百位不能为0
if(i%10==j%10 || i%10==j/10%10 || i%10==j/100) continue;
if(i/10%10==j%10 || i/10%10==j/10%10 || i/10%10==j/100) continue;
if(i/100%10==j%10 || i/100%10==j/10%10 || i/100%10==j/100) continue;
for(int k=123;k<=987;k++){
if(k%10==k/10%10 || k%10==k/100 || k/10%10==k/100) continue;//个 十 百位不能相同
if(k%10==0 || k/10%10==0 || k/100==0) continue;//个 十 百位不能为0
if(i%10==k%10 || i%10==k/10%10 || i%10==k/100) continue;
if(i/10%10==k%10 || i/10%10==k/10%10 || i/10%10==k/100) continue;
if(i/100%10==k%10 || i/100%10==k/10%10 || i/100%10==k/100) continue;
if(j%10==k%10 || j%10==k/10%10 || j%10==k/100) continue;
if(j/10%10==k%10 || j/10%10==k/10%10 || j/10%10==k/100) continue;
if(j/100%10==k%10 || j/100%10==k/10%10 || j/100%10==k/100) continue;
if(i*b==j*a && i*c==k*a && j*c==k*b){
cout<<i<<" "<<j<<" "<<k<<endl;
ans++; //方案数+1
}
}
}
}
if(ans==0) cout<<"No!!!";
return 0;
}
/* Problem: 组成三位数（加强）
Language: C++ Result: 正确 Time: 2026-09-12 15:50:55
User: admin Problem: 2343 contest_id: 0*/
#include<iostream>
using namespace std;
int n,ans=0,a[4010]={6,2,5,5,4,5,6,3,7,6};
//a[i]表示数字i用了多少根火柴棒
int main(){
cin>>n;
for(int i=10;i<=4000;i++) a[i]=a[i/10]+a[i%10];
for(int i=0;i<=2000;i++){ //枚举加数1
for(int j=0;j<=2000;j++){ //枚举加数2
int k=i+j; //和为k
if(a[i]+a[j]+a[k]+4==n){ //火柴棒数量判断
ans++; //方案数+1
//cout<<i<<"+"<<j<<"="<<k<<endl; 观察结果的范围
}
}
}
cout<<ans;
return 0;
}
/*
枚举要素是什么？ 枚举加数1和加数2
每个枚举要素的范围是什么？
*/
/* Problem: 火柴棒等式
Language: C++ Result: 正确 Time: 2026-09-12 15:16:37
User: admin Problem: 1553 contest_id: 0*/
#include<iostream>
using namespace std;
int n,ans=0;
int main(){
cin>>n;
for(int i=0;i<=n;i++){ //枚举a1
for(int j=0;j<=n;j++){ //枚举a2
for(int k=0;k<=n;k++){ //枚举a3
if((i+j)%2==0 && (j+k)%3==0 && (i+j+k)%5==0){
//cout<<i<<" "<<j<<" "<<k<<endl;
ans=max(ans,i+j+k); //取满足要求的最大值
}
}
}
}
cout<<ans;
return 0;
}
/* Problem: 数字方格
Language: C++ Result: 正确 Time: 2026-09-12 14:47:54
User: admin Problem: 1806 contest_id: 0*/
#include<iostream>
using namespace std;
string a,b,c;
int main(){
while(getline(cin,a)){
getline(cin,b);
getline(cin,c);
a=" "+a+" "; //在一句话的首尾都加上空格，这样每个单词前后都有空格了
b=" "+b+" ";
c=" "+c+" ";
while(a.find(b)!=-1){//在a里面找到了b
int p=a.find(b);
a.replace(p,b.size(),c); //从位置p开始，替换掉b的长度，替换为c
}
a.erase(0,1);//在输出前，擦除掉最前面的一个空格
cout<<a<<endl;
}
return 0;
}
/* Problem: 单词替换
Language: C++ Result: 正确 Time: 2026-09-12 14:30:25
User: admin Problem: 1667 contest_id: 0*/
#include<iostream> //解法2：用find函数
using namespace std;
string s,t;
int flag;
int main(){
getline(cin,s); //输入带空格的字符串s
getline(cin,t);
int p=s.find(t); //从头开始找
if(p==-1){//string::npos是一个常数，即-1
cout<<p;
}else{
while(p!=-1){
cout<<p+1<<endl;
p=s.find(t,p+1);//已经找到的位置，往后推一个位置，继续查找（从指定位置开始找）
}
}
return 0;
}
/* Problem: 求子串的位置
Language: C++ Result: 正确 Time: 2026-09-12 14:18:55
User: admin Problem: 1873 contest_id: 0*/
#include<iostream>
using namespace std;
string s,t;
int flag;
int main(){
getline(cin,s); //输入带空格的字符串s
getline(cin,t);
for(int i=0;i<s.size();i++){
string ss=s.substr(i,t.size());//以i为起点，取一个长度为t.size的子串
if(ss==t){
cout<<i+1<<endl;
flag=1; //表示已经找到了至少一个子串位置
}
}
if(!flag) cout<<-1; //flag还是0
return 0;
}
/*
在s从前往后以每个字符i作为起点，取出一个子串（该子串的长度为t的长度）ss;
只需要比较ss是否等于t，如果等于则输出字符的位置i
*/
/* Problem: 求子串的位置
Language: C++ Result: 正确 Time: 2026-09-12 14:08:18
User: admin Problem: 1873 contest_id: 0*/
#include<iostream>
#include<cmath>
using namespace std;
long long n,ans=0;
int main(){
cin>>n;
for(long long i=1;i<=sqrt(n);i++){
if(n%i==0){ //i是n的因子
ans+=2; //因数个数+2,因子是成对的
}
if(i*i==n) ans--; //n正好是完全平方数，所以因子多算了一个，这里减去
}
cout<<ans;
return 0;
}
/* Problem: 因数个数
Language: C++ Result: 正确 Time: 2026-09-12 11:27:34
User: admin Problem: 1088 contest_id: 0*/
#include<iostream>
#include<iomanip>
#include<cmath>
using namespace std;
int main(){
double a,b,c;
cin>>a>>b>>c;
if(a+b<=c || a+c<=b || b+c<=a){
cout<<"false"; //不能构成三角形
return 0; //程序结束
}
double p=(a+b+c)/2;//周长的一半
double s=sqrt(p*(p-a)*(p-b)*(p-c));//面积：海伦公式
cout<<setprecision(1)<<fixed<<s;
return 0;
}
/* Problem: 判断并求三角形的面积
Language: C++ Result: 正确 Time: 2026-09-12 11:05:18
User: admin Problem: 1062 contest_id: 0*/
#include<iostream>
#include<iomanip>
#include<cmath>
using namespace std;
int main(){
double a,b,c;
cin>>a>>b>>c;
double p=(a+b+c)/2;//周长的一半
double s=sqrt(p*(p-a)*(p-b)*(p-c));//面积
cout<<setprecision(2)<<fixed<<s;
return 0;
}
/* Problem: 求三角形面积
Language: C++ Result: 正确 Time: 2026-09-12 10:58:19
User: admin Problem: 1030 contest_id: 0*/
#include<iostream>
#include<iomanip>
#include<cmath>
using namespace std;
int main(){
double x1,x2,y1,y2; //注意y1不要做全局变量
cin>>x1>>y1>>x2>>y2;
double a=x1-x2;
double b=y1-y2;
double c=sqrt(a*a+b*b);//勾股定理
cout<<setprecision(3)<<fixed<<c;
return 0;
}
/* Problem: 平面直角坐标系中两点的距离
Language: C++ Result: 正确 Time: 2026-09-12 10:42:17
User: admin Problem: 1042 contest_id: 0*/
#include<iostream>
using namespace std;
bool prime(int x){//判断整数x是否是质数，是返回true,不是返回false
for(int i=2;i*i<=x;i++){ //枚举到x的平方根
if(x%i==0){
return false; //有因子，不是质数
}
}
return true; //循环结束，都没有找到n的因数
}
int n,cnt=0;
int main(){
cin>>n;
for(int i=2;i<=n;i++){//枚举2~n的所有数字
if(prime(i)){//i是质数
cout<<i<<" ";
cnt++; //质数个数+1
if(cnt%5==0) cout<<endl;
}
}
return 0;
}
/* Problem: n以内的全部素数
Language: C++ Result: 正确 Time: 2026-09-12 10:22:19
User: admin Problem: 1083 contest_id: 0*/
#include<iostream>
using namespace std;
bool prime(int x){//判断整数x是否是质数，是返回true,不是返回false
for(int i=2;i*i<=x;i++){ //枚举到x的平方根
if(x%i==0){
return false; //有因子，不是质数
}
}
return true; //循环结束，都没有找到n的因数
}
int n;
int main(){
scanf("%d",&n);
for(int i=2;i<=n/2;i++){//枚举一个加数
int j=n-i; //直接算出另外一个加数
if(prime(i)&&prime(j)){
printf("%d=%d+%d\n",n,i,j);
}
}
return 0;
}
/* Problem: 哥德巴赫猜想
Language: C++ Result: 正确 Time: 2026-09-12 10:14:21
User: admin Problem: 1156 contest_id: 0*/
#include<iostream> //解法2
using namespace std;
bool prime(int x){//判断整数x是否是质数，是返回true,不是返回false
for(int i=2;i*i<=x;i++){ //枚举到x的平方根
if(x%i==0){
return false; //有因子，不是质数
}
}
return true; //循环结束，都没有找到n的因数
}
int n,ans=0;
int main(){
cin>>n;
if(prime(n)) cout<<"YES";
else cout<<"NO";
return 0;
}
/* Problem: 判断质数(素数)
Language: C++ Result: 正确 Time: 2026-09-12 10:05:02
User: admin Problem: 1152 contest_id: 0*/
#include<iostream> //解法1
using namespace std;
bool prime(int x){//判断整数x是否是质数，是返回true,不是返回false
for(int i=2;i<x;i++){ //枚举2~n-1,判断是否有n的因数
if(x%i==0){
return false; //有因子，不是质数
}
}
return true; //循环结束，都没有找到n的因数
}
int n,ans=0;
int main(){
cin>>n;
if(prime(n)) cout<<"YES";
else cout<<"NO";
return 0;
}
/* Problem: 判断质数(素数)
Language: C++ Result: 正确 Time: 2026-09-12 09:58:34
User: admin Problem: 1152 contest_id: 0*/
#include<iostream>
using namespace std;
int n,ans=0;
int main(){
cin>>n;
for(int i=n+1;;i++){ //枚举范围：n+1 n+2 n+3 ... ,直到正好找到一个各位数字之和为20的数字，则结束
int g=i%10;
int s=i/10%10;
int b=i/100%10;
int q=i/1000%10;
if(g+s+b+q==20){
cout<<i;
break; //或者 return 0;
}
}
return 0;
}
/* Problem: 寻找特殊年号.
Language: C++ Result: 正确 Time: 2026-09-11 20:31:31
User: admin Problem: 2751 contest_id: 0*/
#include<iostream>
using namespace std;
int n,m=0;
int main(){
cin>>n;
for(int i=10;i<=31;i++){//枚举完全平方数
int x=i*i; //完全平方数
int g=x%10;
int s=x/10%10;
int b=x/100%10;
if(g==s || g==b || s==b){ //有两位数字是相同的
m++; //每找到1个，则计数
if(n==m){ //寻找第n个满足条件的
cout<<x;
return 0; //已经找到答案，结束
}
}
}
return 0;
}
/* Problem: 求满足条件的3位数.
Language: C++ Result: 正确 Time: 2026-09-11 20:14:48
User: admin Problem: 3937 contest_id: 0*/