C/C++编程五级 题库
红与黑
有一间长方形的房子,地上铺了红色、黑色两种颜色的正方形瓷砖。你站在其中一块黑色的瓷砖上,只能向相邻的黑色瓷砖移动。请写一个程序,计算你总共能够到达多少块黑色的瓷砖。
时间限制:1000
内存限制:65536
输入
包括多个数据集合。每个数据集合的第一行是两个整数W和H,分别表示x方向和y方向瓷砖的数量。W和H都不超过20。在接下来的H行中,每行包括W个字符。每个字符表示一块瓷砖的颜色,规则如下 1)‘.’:黑色的瓷砖; 2)‘#’:白色的瓷砖; 3)‘@’:黑色的瓷砖,并且你站在这块瓷砖上。该字符在每个数据集合中唯一出现一次。 当在一行中读入的是两个零时,表示输入结束。
输出
对每个数据集合,分别输出一行,显示你从初始位置出发能到达的瓷砖数(记数时包括初始位置的瓷砖)。
样例输入
6 9 ....#. .....# ...... ...... ...... ...... ...... #@...# .#..#. 0 0
样例输出
45
//解法1:深搜
#include <bits/stdc++.h>
using namespace std;
#define N 25
char mp[N][N];//地图
int w, h, ct;//h:行数,w:ct:结果计数
int dir[4][2]={{0,1},{0,-1},{1,0},{-1,0}};//方向数组
bool vis[N][N];
void dfs(int sx, int sy)
{
for(int i = 0; i < 4; ++i)
{
int x = sx + dir[i][0], y = sy + dir[i][1];
if(x >= 1 && x <= h && y >= 1 && y <= w && vis[x][y] == false && mp[x][y] != '#')
{
ct++;
vis[x][y] = true;
dfs(x, y);
}
}
}
int main()
{
int stx, sty;//起始位置
while(true)
{
cin >> w >> h;
if(w == 0 && h == 0)
return 0;
for(int i = 1; i <= h; ++i)
for(int j = 1; j <= w; ++j)
{
cin >> mp[i][j];
if(mp[i][j] == '@')
stx = i, sty = j;
}
memset(vis, 0, sizeof(vis));//多组数据,注意状态还原
ct = 1;
vis[stx][sty] = true;
dfs(stx, sty);
cout << ct << endl;
}
return 0;
}//解法2:广搜
#include <bits/stdc++.h>
using namespace std;
#define N 25
struct Node
{
int x, y;
Node(){}
Node(int a, int b):x(a),y(b){}
};
char mp[N][N];//地图
int w, h;//w:列数 h:行数
int dir[4][2]={{0,1},{0,-1},{1,0},{-1,0}};//方向数组
bool vis[N][N];
int bfs(int sx, int sy)//传入起始位置
{
queue<Node> que;
vis[sx][sy] = true;
que.push(Node(sx, sy));
int ct = 1;//计数,看可以到达几个黑色格子
while(que.empty() == false)
{
Node u = que.front();
que.pop();
for(int i = 0; i < 4; ++i)
{
int x = u.x + dir[i][0], y = u.y + dir[i][1];
if(x >= 1 && x <= h && y >= 1 && y <= w && vis[x][y] == false && mp[x][y] != '#')
{
vis[x][y] = true;
que.push(Node(x, y));
ct++;
}
}
}
return ct;
}
int main()
{
int stx, sty;
while(true)
{
cin >> w >> h;
if(w == 0 && h == 0)
return 0;
for(int i = 1; i <= h; ++i)
for(int j = 1; j <= w; ++j)
{
cin >> mp[i][j];
if(mp[i][j] == '@')
stx = i, sty = j;
}
memset(vis, 0, sizeof(vis));
cout << bfs(stx, sty) << endl;
}
return 0;
}//解法3:
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#define N 1001
using namespace std;
int m,n;
char ch;
int maps[N][N];
int vis[N][N];
int dir[4][2]={{0,1},{0,-1},{1,0},{-1,0}};
int cnt;
void dfs(int x,int y)
{
for(int i=0;i<4;i++)
{
int nx=x+dir[i][0];
int ny=y+dir[i][1];
if(nx>=1&&ny>=1&&nx<=n&&ny<=m&&vis[nx][ny]==0&&maps[nx][ny]==1)
{
vis[nx][ny]=1;
cnt++;
dfs(nx,ny);
}
}
}
int main()
{
while(scanf("%d%d",&m,&n)!=EOF&&m&&n)
{
int x,y;
cnt=1;
memset(vis,0,sizeof(vis));
memset(maps,0,sizeof(maps));
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
{
cin>>ch;
if(ch=='@')
{
x=i;
y=j;
maps[i][j]=1;
}
if(ch=='.')
maps[i][j]=1;
if(ch=='#')
maps[i][j]=0;
}
vis[x][y]=1;
dfs(x,y);
cout<<cnt<<endl;
}
return 0;
}装箱问题
一个工厂制造的产品形状都是长方体,它们的高度都是h,长和宽都相等,一共有六个型号,他们的长宽分别为1*1, 2*2, 3*3, 4*4, 5*5, 6*6。这些产品通常使用一个 6*6*h 的长方体包裹包装然后邮寄给客户。因为邮费很贵,所以工厂要想方设法的减小每个订单运送时的包裹数量。他们很需要有一个好的程序帮他们解决这个问题从而节省费用。现在这个程序由你来设计。
时间限制:1000
内存限制:65536
输入
输入文件包括几行,每一行代表一个订单。每个订单里的一行包括六个整数,中间用空格隔开,分别为1*1至6*6这六种产品的数量。输入文件将以6个0组成的一行结尾。
输出
除了输入的最后一行6个0以外,输入文件里每一行对应着输出文件的一行,每一行输出一个整数代表对应的订单所需的最小包裹数。
样例输入
0 0 4 0 0 1 7 5 1 0 0 0 0 0 0 0 0 0
样例输出
2 1
//解法1:贪心
#include <bits/stdc++.h>
using namespace std;
int status[8][4];//status[i][j]:包裹中已有1个大小为i*i的产品,此时可以最多放入多少个j*j的产品
void initStatus()
{//status[0]:包裹中没有产品时,各种产品最多可以放多少个
status[2][2] = 8;
status[3][2] = 5, status[3][3] = 3;
status[4][2] = 5;
for(int i = 1; i <= 6; ++i)
status[i][1] = 36 - i*i;
}
int pro[8];//pro[i]:i*i产品的数量
int main()
{
initStatus();
while(true)
{
int sum = 0, bag = 0, rem[8];//sum:总产品数量 bag:包裹数 rem[i]:当前剩余空间能放几个i*i
for(int i = 1; i <= 6; ++i)
{
cin >> pro[i];
sum += pro[i];
}
if(sum == 0)//如果6个数都是0,那么加和为0,要跳出循环
break;
for(int i = 6; i >= 1; --i)
{
while(pro[i] > 0)
{
bag++;//用一个新包裹放i*i
pro[i]--;
for(int j = 1; j <= 3; ++j)//获取当前剩余空间情况
rem[j] = status[i][j];
int j = 3;
while(j >= 1)
{
if(rem[j] > 0 && pro[j] > 0)//如果可以放j*j的产品
{
pro[j]--;//放一个产品
if(j == 3)
{
rem[3]--;
rem[2] -= 2;
rem[1] -= 9;
}
else if(j == 2)
{
rem[2]--;
rem[1] -= 4;
}
else//j == 1
rem[1]--;
}
else
--j;
}
}
}
cout << bag << endl;
}
return 0;
}//解法2:手动完成贪心过程
#include<bits/stdc++.h>
using namespace std;
int bag;//总包裹数
int k[4] = {0, 5, 3, 1};//k[i]表示3*3的产品有i个时(k[0]表示有4个时)剩余空间可以放2*2产品的个数
int pro[8], p2, p1;//p2:2*2空位数 p1:1*1空位数
int main()
{
while(true)
{
for(int i = 1; i <= 6; ++i)
cin >> pro[i];
if(pro[1] == 0 && pro[2] == 0 && pro[3] == 0 && pro[4] == 0 && pro[5] == 0 && pro[6] == 0)
break;
bag = pro[6] + pro[5] + pro[4] + ceil(pro[3]/4.0);//6*6和5*5和4*4一定是一个占一个箱子,而3*3 4个占一个箱子
p2 = 5*pro[4]+k[pro[3]%4];//k[pro[3]%4]:有pro[3]%4个3*3在一个包裹中时,剩下的位置可以放2*2的数目
if(pro[2] > p2)//2*2的个数比我们留出来为2*2的空间个数多,就需要为2*2另开箱子
bag += ceil((pro[2]-p2)/9.0);//多出来的2*2箱子应该占用的新箱子数
p1 = 36*bag-36*pro[6]-25*pro[5]-16*pro[4]-9*pro[3]-4*pro[2];//求出当前包裹中所有剩下的可以放1*1的位置数
if(pro[1] > p1)//如果1*1的个数,比我们留出的空间多就需要另开空间
bag += ceil((pro[1]-p1)/36.0);//将多出来的另开箱子
cout << bag << endl;
}
return 0;
}//解法3:
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
#define INF 999999999
#define N 101
using namespace std;
int main()
{
int a,b,c,d,e,f;
int g[4]={0,5,3,1};
int x,y;
while(cin>>a>>b>>c>>d>>e>>f)
{
if(a+b+c+d+e+f==0)
break;
int n=f+e+d+(c+3)/4;
x=5*d+g[c%4];
if(b>x)
n+=(b-x+8)/9;
y=36*n-36*f-25*e-16*d-9*c-4*b;
if(a>y)
n+=(a-y+35)/36;
cout<<n<<endl;
}
return 0;
}课程表
现在你总共有n门课需要选,记为0到n-1。在选修某些课程之前需要一些先修课程。例如,想要学习课程0,你需要先完成课程1,我们用一个匹配来表示他们:[0, 1]。给定课程总量以及它们的先决条件,判断是否可能完成所有课程的学习?
时间限制:1000
内存限制:65536
输入
多组数据。每组数据第一行是n和m,n表示有n门课程,m表示有m组依赖关系,接下来的m行是依赖关系的具体信息a b,表示第a门课程依赖第b门课程。 0<=n <=1000,0 <= m <= 4000 两组数据之间可能有空行
输出
对每组数据,能完成输出 True,不能完成输出 False
样例输入
2 1 1 0 2 2 1 0 0 1
样例输出
True False 提示
示例2解释: 总共有2门课程。学习课程1之前,你需要先完成课程0;并且学习课程0之前,你还应先完成课程1。这是不可能的。
//拓扑排序:Kahn算法+邻接表+栈
#include <bits/stdc++.h>
using namespace std;
int n,m;
int a[1005][1005];//邻接点
int rd[1005],cd[1005];//入度 出度
int main()
{
int r,c,num,i,j,k;
stack<int> st;
while(cin>>n>>m){
memset(a,0,sizeof(a));
memset(rd,0,sizeof(rd));
memset(cd,0,sizeof(cd));
while(!st.empty()) st.pop();
for(i=1;i<=m;i++){
cin>>r>>c;
rd[c]++;
cd[r]++;
a[r][cd[r]]=c;
}
for(i=0;i<=n-1;i++)
if(rd[i]==0){
st.push(i);
}
num=0;
while(!st.empty()){
i=st.top();
st.pop();
num++;
for(j=1;j<=cd[i];j++){
k=a[i][j];
rd[k]--;
if(rd[k]==0)st.push(k);
}
}
if(num==n) cout<<"True"<<endl;
else cout<<"False"<<endl;
}
return 0;
}最小新整数
给定一个十进制正整数n(0 < n < 1000000000),每个数位上数字均不为0。n的位数为m。 现在从m位中删除k位(0<k < m),求生成的新整数最小为多少? 例如: n = 9128456, k = 2, 则生成的新整数最小为12456
时间限制:1000
内存限制:65536
输入
第一行t, 表示有t组数据; 接下来t行,每一行表示一组测试数据,每组测试数据包含两个数字n, k。
输出
t行,每行一个数字,表示从n中删除k位后得到的最小整数。
样例输入
2 9128456 2 1444 3
样例输出
12456 1
//解法1:每次找k+1个数中的最小值
#include<bits/stdc++.h>
using namespace std;
#define N 15
int main()
{
int k, t;
char s[N], a[N];
cin >> t;
while(t--)
{
cin >> s >> k;
int an = 0, len = strlen(s), i = 0;
while(i < len)
{
if(k == len-i)//如果剩下的元素个数只有k个,那么都删掉
break;
int mi = i;//求i~i+k的最小值下标
for(int j = i; j <= i+k; ++j)
{
if(s[j] < s[mi])
mi = j;
}
a[++an] = s[mi];
k -= mi - i;//s[i]~s[mi-1]都删掉,删掉了mi-i个元素
i = mi + 1;
}
for(i = 1; i <= an; ++i)
cout << a[i];
cout << endl;
}
return 0;
}//解法2:删掉比后面数字大的数字
#include<bits/stdc++.h>
using namespace std;
#define N 15
int main()
{
int k, t;
char s[N], a[N];
cin >> t;
while(t--)
{
cin >> s >> k;
int an = 0, len = strlen(s), ct = 0;
for(int i = 0; i < len; ++i)
{
while(an > 0 && a[an] > s[i] && ct < k)//a[an]为前一个数 s[i]为后一个数,当a[an]>s[i]时,删除a[an]
{
an--;
ct++;//删除数字个数加1
}
a[++an] = s[i];//无论如何s[i]都会填充进数组a
}
while(ct < k)//删除末尾的k-ct个元素
{
an--;
ct++;
}
for(int i = 1; i <= an; ++i)
cout << a[i];
cout << endl;
}
return 0;
}//解法3:
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
#define INF 999999999
#define N 101
using namespace std;
char str[N];
int main()
{
int t,n;
cin>>t;
while(t--)
{
cin>>str>>n;
int len=strlen(str);
while(n--)
{
for(int i=0;i<len-1;i++)
if(str[i]>str[i+1])
{
for(int j=i;j<len-1;j++)
str[j]=str[j+1];
break;
}
len--;
}
str[len]='\0';
cout<<str<<endl;
}
return 0;
}书架(2023.12)
John最近买了一个书架用来存放奶牛养殖书籍,但书架很快被存满了,只剩最顶层有空余。
John共有N头奶牛(1 ≤ N ≤ 20,000),每头奶牛有自己的高度Hi(1 ≤ Hi ≤ 10,000),N头奶牛的总高度为S。书架高度为B(1 ≤ B ≤ S < 2,000,000,007).
为了到达书架顶层,奶牛可以踩着其他奶牛的背,像叠罗汉一样,直到他们的总高度不低于书架高度。当然若奶牛越多则危险性越大。为了帮助John到达书架顶层,找出使用奶牛数目最少的解决方案吧。
时间限制:10000
内存限制:65536
输入
第1行:空格隔开的整数N和B 第2~N+1行:第i+1行为整数Hi
输出
能达到书架高度所使用奶牛的最少数目
样例输入
6 40 6 18 11 13 19 11
样例输出
3
// 参考代码1
#include <algorithm>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <iostream>
#define INF 999999999
#define N 20001
using namespace std;
int a[N];
void qsort(int x, int y) {
int i = x, j = y, mid = a[(x + y) / 2];
while (i <= j) {
while (a[i] > mid)
i++;
while (a[j] < mid)
j--;
if (i <= j) {
swap(a[i], a[j]);
i++;
j--;
}
}
if (x < j)
qsort(x, j);
if (i < y)
qsort(i, y);
}
int main() {
int n, b;
int sum = 0;
int i;
cin >> n >> b;
for (i = 1; i <= n; i++)
cin >> a[i];
qsort(1, n);
for (i = 1; i <= n; i++) {
sum += a[i];
if (sum >= b)
break;
}
cout << i << endl;
;
return 0;
}// 参考代码2
#include <bits/stdc++.h>
using namespace std;
int n, b, a[20002];
int main() {
cin >> n >> b;
for (int i = 0; i < n; i++)
cin >> a[i];
sort(a, a + n);
long long s = 0;
for (int i = n - 1; i >= 0; i--) {
s += a[i];
if (s >= b) {
cout << n - i << endl;
return 0;
}
}
return 0;
}鸣人和佐助(2023.12)
描述
佐助被大蛇丸诱骗走了,鸣人在多少时间内能追上他呢?
已知一张地图(以二维矩阵的形式表示)以及佐助和鸣人的位置。地图上的每个位置都可以走到,只不过有些位置上有大蛇丸的手下,需要先打败大蛇丸的手下才能到这些位置。鸣人有一定数量的查克拉,每一个单位的查克拉可以打败一个大蛇丸的手下。假设鸣人可以往上下左右四个方向移动,每移动一个距离需要花费1个单位时间,打败大蛇丸的手下不需要时间。如果鸣人查克拉消耗完了,则只可以走到没有大蛇丸手下的位置,不可以再移动到有大蛇丸手下的位置。佐助在此期间不移动,大蛇丸的手下也不移动。请问,鸣人要追上佐助最少需要花费多少时间?
输入
输入的第一行包含三个整数:M,N,T。代表M行N列的地图和鸣人初始的查克拉数量T。0 < M,N < 200,0 ≤ T < 10
后面是M行N列的地图,其中@代表鸣人,+代表佐助。*代表通路,#代表大蛇丸的手下。
输出
输出包含一个整数R,代表鸣人追上佐助最少需要花费的时间。如果鸣人无法追上佐助,则输出-1。
样例输入1
4 4 1 #@## **## ###+ ****
样例输入2
4 4 2 #@## **## ###+ ****
样例输出1
6
样例输出2
4
#include <bits/stdc++.h>
using namespace std;
int n, m, t, s2[10][256][256], fx[4][2] = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
char s1[256][256];
struct AAA {
int i;
int j;
int bs;
int st;
};
int bfs() {
int i, j, k, ti, tj, ret = -1;
queue<AAA> dl;
AAA tmp, tmp1;
for (i = 0; i < m; i++) {
for (j = 0; j < n; j++)
if (s1[i][j] == '@') {
tmp.i = i;
tmp.j = j;
tmp.bs = 0;
tmp.st = t;
break;
}
if (j < n)
break;
}
dl.push(tmp);
for (i = 0; i < 10; i++)
for (j = 0; j < m; j++)
for (k = 0; k < n; k++)
s2[i][j][k] = 0;
s2[0][tmp.i][tmp.j] = 1;
while (!dl.empty()) {
tmp = dl.front();
dl.pop();
if (s1[tmp.i][tmp.j] == '+') {
ret = tmp.bs;
break;
}
for (i = 0; i < 4; i++) {
ti = tmp.i + fx[i][0];
tj = tmp.j + fx[i][1];
if ((ti < 0) || (ti >= m) || (tj < 0) || (tj >= n))
continue;
if (s2[t - tmp.st][ti][tj] == 1)
continue;
if ((s1[ti][tj] == '#') && (tmp.st == 0))
continue;
s2[t - tmp.st][ti][tj] = 1;
tmp1.i = ti;
tmp1.j = tj;
tmp1.bs = tmp.bs + 1;
tmp1.st = tmp.st;
if (s1[ti][tj] == '#')
tmp1.st--;
dl.push(tmp1);
}
}
return ret;
}
int main() {
int i, j, k;
char tmp[16];
gets(tmp);
sscanf(tmp, "%d%d%d", &m, &n, &t);
for (i = 0; i < m; i++)
gets(s1[i]);
printf("%d", bfs());
return 0;
}//参考代码2
#include<stdio.h>
#include<algorithm>
#include<string.h>
using namespace std;
const int inf=0x3f3f3f3f;
int n,m,sx,sy,st,minstep=inf;
int step[201][201][11],dx[]={0,1,-1,0},dy[]={1,0,0,-1};
char mp[201][201];
bool vis[201][201];
void dfs(int x,int y,int t,int stp)
{
if(x<1 || x>n || y<1 || y>m || vis[x][y]) return ;
if(t<0) return ;
if(stp>=minstep) return ;
if(stp>=step[x][y][t]) return ;
step[x][y][t]=stp;
if(mp[x][y]=='#') t--;
else if(mp[x][y]=='+') {
if(stp<minstep) minstep=stp;
return ;
}
vis[x][y]=1;
for(int i=0;i<4;++i){
int nx=x+dx[i];
int ny=y+dy[i];
dfs(nx,ny,t,stp+1);
}
vis[x][y]=0;
}
int main()
{
scanf("%d%d%d",&n,&m,&st);
getchar();
for(int i=1;i<=n;++i){
for(int j=1;j<=m;++j){
scanf("%c",&mp[i][j]);
if(mp[i][j]=='@') {
sx=i;
sy=j;
}
}
getchar();
}
memset(step,0x3f,sizeof(step));
dfs(sx,sy,st,0);
if(minstep==inf) printf("-1");
else printf("%d",minstep);
return 0;
}//参考代码3
#include<cstdio>
#include<queue>
using namespace std;
struct POINT
{
int x,y,tot,T;
} point;
queue<POINT> que;
int main()
{
bool walked[205][205][15]={};
int r,c,T,F[4][2]={{-1,0},{1,0},{0,-1},{0,1}};
scanf("%d%d%d",&r,&c,&T);
char maze[205][205]={};
for(int i=0;i<r;i++)
{
scanf("%s",maze[i]);
for(int j=0;j<c;j++)
if(maze[i][j]=='@')
{
point.x=i;point.y=j;
point.tot=0;point.T=T;
}
}
que.push(point);
while(!que.empty())
{
for(int i=0;i<4;i++)
{
point.x=que.front().x+F[i][0];
point.y=que.front().y+F[i][1];
point.tot=que.front().tot+1;
point.T=que.front().T;
if(point.x<0 || point.x>=r || point.y<0 || point.y>=c || walked[point.x][point.y][point.T]) continue;
if(maze[point.x][point.y]=='#')
if(point.T) point.T--;
else continue;
if(maze[point.x][point.y]=='+') {printf("%d\n",point.tot);return 0;}
walked[point.x][point.y][point.T]=true;
que.push(point);
}
que.pop();
}
printf("-1\n");
return 0;
}// 参考代码4
#include <bits/stdc++.h>
using namespace std;
char a[202][202];
int v_ckl[202][202]; // 走到该坐标点时的最小消耗的查克拉
struct nod {
int x, y, ckl, step;
};
int dx[4] = {-1, 1, 0, 0};
int dy[4] = {0, 0, -1, 1};
int main() {
int n, m, k, mi, mj;
cin >> m >> n >> k;
for (int i = 1; i <= m; i++)
for (int j = 1; j <= n; j++) {
cin >> a[i][j];
if (a[i][j] == '@') {
mi = i;
mj = j;
}
}
queue<nod> q;
q.push({mi, mj, k, 0});
v_ckl[mi][mj] = k;
memset(v_ckl, -1,
sizeof(v_ckl)); // 注意:初始值 查克拉为零时条件允许也可以走的
while (!q.empty()) {
nod t = q.front();
q.pop();
for (int i = 0; i < 4; i++) {
if (t.x + dx[i] < 1 || t.x + dx[i] > m || t.y + dy[i] < 1 ||
t.y + dy[i] > n)
continue;
else if (a[t.x + dx[i]][t.y + dy[i]] == '+') {
cout << t.step + 1;
return 0;
} // 注意:比较查克拉值 好判断该点是否需要更新
else if (a[t.x + dx[i]][t.y + dy[i]] == '*' &&
t.ckl > v_ckl[t.x + dx[i]][t.y + dy[i]]) {
q.push({t.x + dx[i], t.y + dy[i], t.ckl, t.step + 1});
v_ckl[t.x + dx[i]][t.y + dy[i]] = t.ckl;
} else if (a[t.x + dx[i]][t.y + dy[i]] == '#' && t.ckl > 0 &&
t.ckl > v_ckl[t.x + dx[i]][t.y + dy[i]]) {
q.push({t.x + dx[i], t.y + dy[i], t.ckl - 1, t.step + 1});
v_ckl[t.x + dx[i]][t.y + dy[i]] = t.ckl - 1;
}
}
}
cout << "-1";
return 0;
}献给阿尔吉侬的花束
阿尔吉侬是一只聪明又慵懒的小白鼠,它最擅长的就是走各种各样的迷宫。今天它要挑战一个非常大的迷宫,研究员们为了鼓励阿尔吉侬尽快到达终点,就在终点放了一块阿尔吉侬最喜欢的奶酪。现在研究员们想知道,如果阿尔吉侬足够聪明,它最少需要多少时间就能吃到奶酪。
迷宫用一个R×C的字符矩阵来表示。字符S表示阿尔吉侬所在的位置,字符E表示奶酪所在的位置,字符#表示墙壁,字符.表示可以通行。阿尔吉侬在1个单位时间内可以从当前的位置走到它上下左右四个方向上的任意一个位置,但不能走出地图边界。
时间限制:100
内存限制:65536
输入
第一行是一个正整数T(1 <= T <= 10),表示一共有T组数据。 每一组数据的第一行包含了两个用空格分开的正整数R和C(2 <= R, C <= 200),表示地图是一个R×C的矩阵。 接下来的R行描述了地图的具体内容,每一行包含了C个字符。字符含义如题目描述中所述。保证有且仅有一个S和E。
输出
对于每一组数据,输出阿尔吉侬吃到奶酪的最少单位时间。若阿尔吉侬无法吃到奶酪,则输出“oop!”(只输出引号里面的内容,不输出引号)。每组数据的输出结果占一行。
样例输入
3 3 4 .S.. ###. ..E. 3 4 .S.. .E.. .... 3 4 .S.. #### ..E.
样例输出
5 1 oop!
#include <bits/stdc++.h>
using namespace std;
char a[202][202];
struct nod {
int x, y, step;
};
int dx[4] = {-1, 1, 0, 0};
int dy[4] = {0, 0, -1, 1};
int main() {
int t, r, c, mi, mj;
cin >> t;
while (t--) {
cin >> r >> c;
memset(a, 0, sizeof(a));
for (int i = 1; i <= r; i++)
for (int j = 1; j <= c; j++) {
cin >> a[i][j];
if (a[i][j] == 'S') {
mi = i;
mj = j;
}
}
queue<nod> q;
q.push({mi, mj, 0});
bool is_t = false;
while (!q.empty()) {
nod t = q.front();
q.pop();
for (int i = 0; i < 4; i++) {
if (t.x + dx[i] < 1 || t.x + dx[i] > r || t.y + dy[i] < 1 ||
t.y + dy[i] > c)
continue;
else if (a[t.x + dx[i]][t.y + dy[i]] == '#')
continue;
else if (a[t.x + dx[i]][t.y + dy[i]] == 'E') {
cout << t.step + 1 << endl;
is_t = true;
break;
} else if (a[t.x + dx[i]][t.y + dy[i]] == '.') {
q.push({t.x + dx[i], t.y + dy[i], t.step + 1});
a[t.x + dx[i]][t.y + dy[i]] = '#';
}
}
if (is_t)
break;
}
if (!is_t)
cout << "oop!" << endl;
}
return 0;
}逃离迷宫(2024-3-5级)
你在一个地下迷宫中找到了宝藏,但是也触发了迷宫机关,导致迷宫将在T分钟后坍塌,为此你需要在T分钟内逃离迷宫,你想知道你能不能逃离迷宫。迷宫是一个边长为m的正方形,其中"S"表示你所在的位置,"E"表示迷宫出口,"."是可以随意走动的区域,"#"是不可穿行的墙壁,每次你可以耗费1分钟在区域间移动(上下左右四个方向)。
时间限制:1000
内存限制:65536
输入
输入包含多组数组,第一行是一个整数K(1 <= K <= 10),表示有K组数据。接下来每组数组包含整数m(2<=m<=10)和整数T,m表示正方形迷宫的边长,T表示坍塌时间。其后是一个m*m的字符矩阵,包含字符"S", "E", "."和"#"。
输出
每组数据输出一行,输出“YES"或者"NO",表示是否可以在坍塌之前逃离(也就是说移动次数是否可以不超过T)。
样例输入
2 4 7 S... ###. .#E. ..#. 3 4 S.. ..# .#E
样例输出
YES NO
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include <string.h>
#define MAX_M 12
struct node {
int x, y;
int tcnt;
};
int m, t;
char mat[MAX_M][MAX_M];
int bfs(int x0, int y0, int x1, int y1) {
if (x0 == x1 && y0 == y1) {
return 0;
}
struct node nd = {x0, y0, 0};
int x, y;
struct node q[MAX_M * MAX_M];
int front = 0, rear = 0;
q[rear++] = nd;
while (front < rear) {
nd = q[front++];
x = nd.x;
y = nd.y;
if (x < m - 1) {
if (mat[x + 1][y] == 'E') {
return nd.tcnt + 1;
} else if (mat[x + 1][y] == '.') {
struct node newNode = {x + 1, y, nd.tcnt + 1};
q[rear++] = newNode;
mat[x + 1][y] = '*';
}
}
if (x > 0) {
if (mat[x - 1][y] == 'E') {
return nd.tcnt + 1;
} else if (mat[x - 1][y] == '.') {
struct node newNode = {x - 1, y, nd.tcnt + 1};
q[rear++] = newNode;
mat[x - 1][y] = '*';
}
}
if (y < m - 1) {
if (mat[x][y + 1] == 'E') {
return nd.tcnt + 1;
} else if (mat[x][y + 1] == '.') {
struct node newNode = {x, y + 1, nd.tcnt + 1};
q[rear++] = newNode;
mat[x][y + 1] = '*';
}
}
if (y > 0) {
if (mat[x][y - 1] == 'E') {
return nd.tcnt + 1;
} else if (mat[x][y - 1] == '.') {
struct node newNode = {x, y - 1, nd.tcnt + 1};
q[rear++] = newNode;
mat[x][y - 1] = '*';
}
}
}
return -1;
}
int main() {
int k, i, j, x0, y0, x1, y1, ans;
scanf("%d", &k);
while (k--) {
scanf("%d %d", &m, &t);
for (i = 0; i < m; i++) {
for (j = 0; j < m; j++) {
scanf(" %c", &mat[i][j]);
if (mat[i][j] == 'S') {
x0 = i;
y0 = j;
} else if (mat[i][j] == 'E') {
x1 = i;
y1 = j;
}
}
}
ans = bfs(x0, y0, x1, y1);
if (ans <= t && ans >= 0) {
printf("YES\n");
} else {
printf("NO\n");
}
}
return 0;
}密室逃脱(2024-3-5级)
小Y喜欢玩密室逃脱,每次游戏开始时,小Y会进入一个密室,她需要按照顺序解开各个隐藏线索才能成功逃脱密室。小Y非常聪明,解开线索对她来说并不难,但是她有一点懒,她希望在通关过程中移动次数最少。请你帮小Y计算她至少要移动多少次才能成功通关。
密室是m行n列的格子矩阵,小Y从左上角(1,1)进入密室,密室中有三种格子:
墙,以数字0标记
路,以数字1标记
隐藏线索处,以数字( > 1)标记, 代表该线索的难度
小Y需要按照难度递增的顺序解开各个线索,逃脱密室。
时间限制:1000
内存限制:65536
输入
第一行是一个整数 T,表示输入包含 T 组数据,分别是不同的游戏中小Y所处的密室。 对于每组数据,第一行包括两个整数:m(1 <= m <= 100)、n(1 <= n <= 100)。 接下来 m 行,每行有n个数字,第 i 行的第 j 个数字表示密室中第 i 行第 j 列的格子的类型。 题目保证进入密室处(1,1)不是墙壁,线索的难度都不相同。
输出
对于每组数据,你需要输出一个整数,表示小Y在这个密室中至少要移动多少次才能成功通关。 如果小Y不可能解开所有线索,输出-1.
样例输入
2 3 3 1 3 2 1 0 4 10 6 5 3 3 1 3 2 0 0 0 10 6 5
样例输出
8 -1
提示
样例解释:由于需要按难度顺序解开线索,在第一组数据中,小Y第一次移动到3时不能解密,在完成2之后需要回到3.最后小Y解开10时,她成功通关。
//示例代码1 条件+广搜
#include <iostream>
#include <cstring>
#include <algorithm>
#include <queue>
using namespace std;
int m,n;
int maze[104][104] = {};
int dx[4] = {0,0,-1,1};
int dy[4] = {-1,1,0,0};
bool legal(int x, int y){
if(0 <= x && x< m && 0 <= y && y < n && maze[x][y] != 0)return 1;
return 0;
}
struct Node{
int x, y, k, t;
};
int main()
{
int T;
cin >> T;
while(T--){
memset(maze, 0, sizeof(maze));
int vis[104][104] = {};
memset(vis, 0xff, sizeof(vis));
int S[10050] = {};
int cnt = 0;
cin >> m >> n;
for(int i = 0; i < m; ++i){
for(int j = 0; j < n; ++j){
cin >> maze[i][j];
if (maze[i][j] > 1) {
S[cnt++] = maze[i][j];
}
}
}
queue<Node> open;
sort(S, S + cnt);
if (maze[0][0] == S[0]) {
open.push({0, 0, 1, 0});
vis[0][0] = 1;
}
else {
open.push({0, 0, 0, 0});
vis[0][0] = 0;
}
bool flag = 0;
while (!open.empty()) {
Node temp = open.front();
open.pop();
if (temp.k == cnt) {
flag = 1;
cout << temp.t << endl;
break;
}
for (int i = 0; i < 4; i++) {
int x = temp.x + dx[i], y = temp.y + dy[i], k = temp.k;
if (!legal(x,y)) continue;
if (maze[x][y] == S[k]) k++;
if (vis[x][y] >= k) continue;
vis[x][y] = k;
open.push({x, y, k, temp.t + 1});
}
}
if (!flag) cout << -1 << endl;
}
return 0;
}//参考代码2
#include <iostream>
#include <algorithm>
#include <queue>
#include <cstring>
using namespace std;
int m,n;
int maze[104][104] = {};
int dx[4] = {0,0,-1,1};
int dy[4] = {-1,1,0,0};
bool legal(int x, int y){
if(0 <= x && x< m && 0 <= y && y < n && maze[x][y] != 0)
return 1;
return 0;
}
struct Node{
int x, y, k, t;
};
int main()
{
int T;
cin >> T;
while(T--){
memset(maze, 0, sizeof(maze));
int vis[104][104] = {};
memset(vis, 0xff, sizeof(vis));
int S[10050] = {};
int cnt = 0;
cin >> m >> n;
for(int i = 0; i < m; ++i){
for(int j = 0; j < n; ++j){
cin >> maze[i][j];
if (maze[i][j] > 1) {
S[cnt++] = maze[i][j];
}
}
}
queue<Node> open;
sort(S, S + cnt);
if (maze[0][0] == S[0]) {
open.push({0, 0, 1, 0});
vis[0][0] = 1;
}
else {
open.push({0, 0, 0, 0});
vis[0][0] = 0;
}
bool flag = 0;
while (!open.empty()) {
Node temp = open.front();
open.pop();
if (temp.k == cnt) {
flag = 1;
cout << temp.t << endl;
break;
}
for (int i = 0; i < 4; i++) {
int x = temp.x + dx[i], y = temp.y + dy[i], k = temp.k;
if (!legal(x,y))
continue;
if (maze[x][y] == S[k])
k++;
if (vis[x][y] >= k)
continue;
vis[x][y] = k;
open.push({x, y, k, temp.t + 1});
}
}
if (!flag)
cout << -1 << endl;
}
return 0;
}交易市场(2024-3-5级)
市场里面一共有n种物品,有m种交易途径,每个交易途径可以由(x,y,z)表示,意思是可以用第x种物品换成第y种物品,并且得到z元的收益(z均大于0)。最开始你只有第一种物品,请问最多可以赚取多少收益。
时间限制:1000
内存限制:65536
输入
第一行两个正整数n和m(n ≤ 1000,m ≤ 4000) 接下来m行,每行三个正整数x, y, z,意思是可以用第x种物品换成第y种物品,并且得到z元的收益。(1 ≤ x,y ≤ n, 1 ≤ z ≤ 100)
输出
一个整数表示最大收益,如果可以赚取无穷多的收益则输出1000000000
样例输入
3 3 1 2 2 2 3 3 1 3 4
样例输出
5
//参考代码1
#include <algorithm>
#include <cstring>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <vector>
#define INF 1000000000
using namespace std;
struct exchangeTo {
int target;
int p;
exchangeTo(int a, int b) : target(a), p(b) {}
};
struct path {
int pre;
int val;
} dp[1005];
map<int, vector<exchangeTo>> tables;
bool inPath(int n, int k) {
while (k != -1) {
if (n == k)
return true;
k = dp[k].pre;
}
return false;
}
int main() {
memset(dp, -1, sizeof(dp));
int n, m;
cin >> n >> m;
for (int i = 0; i < m; i++) {
int x, y, z;
cin >> x >> y >> z;
tables[x].push_back(exchangeTo(y, z));
}
dp[1].val = 0, dp[1].pre = 0;
bool done = false;
int result = 0;
queue<int> myqueues;
myqueues.push(1);
while (!myqueues.empty()) {
int top = myqueues.front();
myqueues.pop();
if (!tables[top].empty()) {
vector<exchangeTo>::iterator ii;
for (ii = tables[top].begin(); ii != tables[top].end(); ii++) {
if (inPath(ii->target, top)) {
result = INF;
done = true;
break;
}
if (dp[top].val + ii->p > dp[ii->target].val) {
dp[ii->target].val = dp[top].val + ii->p;
dp[ii->target].pre = top;
myqueues.push(ii->target); // 注意这里的更新
}
result = max(result, dp[ii->target].val);
}
if (done)
break;
}
}
cout << result << endl;
return 0;
}//参考代码2
#include <iostream>
#include <vector>
#include <map>
#include <set>
#include <cstring>
#include <algorithm>
#include <queue>
#define INF 1000000000
using namespace std;
struct exchangeTo {
int target;
int p;
exchangeTo(int a, int b) :target(a), p(b) {}
};
struct path {
int pre;
int val;
}dp[1005];
map<int, vector<exchangeTo> >tables;
bool inPath(int n, int k) {
while (k != -1) {
if (n == k)
return true;
k = dp[k].pre;
}
return false;
}
int main() {
memset(dp, -1, sizeof(dp));
int n, m;
cin >> n >> m;
for (int i = 0; i < m; i++) {
int x, y, z;
cin >> x >> y >> z;
tables[x].push_back(exchangeTo(y, z));
}
dp[1].val = 0, dp[1].pre = 0;
bool done = false;
int result = 0;
queue<int>myqueues;
myqueues.push(1);
while (!myqueues.empty()) {
int top = myqueues.front();
myqueues.pop();
if (!tables[top].empty()) {
vector<exchangeTo>::iterator ii;
for (ii = tables[top].begin(); ii != tables[top].end(); ii++) {
if (inPath(ii->target, top))
{
result = INF;
done = true;
break;
}
if (dp[top].val + ii->p > dp[ii->target].val) {
dp[ii->target].val = dp[top].val + ii->p;
dp[ii->target].pre = top;
myqueues.push(ii->target);
}
result = max(result, dp[ii->target].val);
}
if (done)break;
}
}
cout << result << endl;
return 0;
}求逆序对问题(2024-3-5级)
给定N个数的序列a1,a2,...aN,定义一个数对(ai, aj)为“重要逆序对”的充要条件为 i < j 且 ai > 2aj。求给定序列中“重要逆序对”的个数。
时间限制:1000
内存限制:256000
输入
本题有多个测试点,每个测试点分为两行:第一行为序列中数字的个数N(1 ≤ N ≤ 200000),第二行为序列a1, a2 ... aN(0 ≤a ≤ 10000000),由空格分开。N=0表示输入结束。
输出
每个测试点一行,输出一个整数,为给序列中“重要逆序对”的个数。
样例输入
10
0 9 8 7 6 5 4 3 2 1
0
样例输出
16
提示
请注意答案范围,如果使用printf输出long long类型,请用%lld
//参考代码1
#include <iostream>
using namespace std;
int arr[200005];
int tmp[200005];
int N;
long long mergesort(int start, int end) {
long long cnt = 0, mid = (start + end) / 2;
if (start >= end)
return 0;
cnt += mergesort(start, mid);
cnt += mergesort(mid + 1, end);
// find important reverse pair
int i = start, j = mid + 1;
while (i <= mid && j <= end) {
if (arr[i] > 2 * arr[j] && j <= end) {
cnt += (mid - i + 1);
j++;
} else {
i++;
}
}
// merge sort
i = start, j = mid + 1;
int idx = 0;
while (i <= mid && j <= end) {
if (arr[i] > arr[j]) {
tmp[idx++] = arr[j++];
} else {
tmp[idx++] = arr[i++];
}
}
while (i <= mid)
tmp[idx++] = arr[i++];
while (j <= end)
tmp[idx++] = arr[j++];
for (int k = 0; k < idx; k++) {
arr[start + k] = tmp[k];
}
return cnt;
}
int main() {
while (cin >> N) {
if (N == 0)
break;
for (int i = 1; i <= N; i++) {
cin >> arr[i];
}
cout << mergesort(1, N) << endl;
}
return 0;
}//参考代码2
#include <iostream>
using namespace std;
int arr[200005];
int tmp[200005];
int N;
long long mergesort(int start,int end){
long long cnt=0, mid=(start+end)/2;
if(start>=end) return 0;
cnt+=mergesort(start,mid);
cnt+=mergesort(mid+1,end);
int i=start,j=mid+1;
while(i<=mid && j<=end){
if(arr[i]>2*arr[j] && j<=end){
cnt+=(mid-i+1);
j++;
}else{
i++;
}
}
i=start,j=mid+1;
int idx=0;
while(i<=mid && j<=end){
if(arr[i]>arr[j]){
tmp[idx++]=arr[j++];
}else{
tmp[idx++]=arr[i++];
}
}
while(i<=mid) tmp[idx++]=arr[i++];
while(j<=end) tmp[idx++]=arr[j++];
for(int k=0;k<idx;k++){
arr[start+k]=tmp[k];
}
return cnt;
}
int main(){
while(cin>>N){
if(N==0) break;
for(int i=1;i<=N;i++){
cin>>arr[i];
}
cout<<mergesort(1,N)<<endl;
}
return 0;
}拯救007
在老电影“007之生死关头”(Live and Let Die)中有一个情节,007被毒贩抓到一个鳄鱼池中心的小岛上,他用了一种极为大胆的方法逃脱 —— 直接踩着池子里一系列鳄鱼的大脑袋跳上岸去!(据说当年替身演员被最后一条鳄鱼咬住了脚,幸好穿的是特别加厚的靴子才逃过一劫。)
设鳄鱼池是长宽为100米的方形,中心坐标为 (0, 0),且东北角坐标为 (50, 50)。池心岛是以 (0, 0) 为圆心、直径15米的圆。给定池中分布的鳄鱼的坐标、以及007一次能跳跃的最大距离,你需要告诉他是否有可能逃出生天。
时间限制:6000
内存限制:262144
输入
首先第一行给出两个正整数:鳄鱼数量 N(≤ 100)和007一次能跳跃的最大距离 D。随后 N 行,每行给出一条鳄鱼的 (x, y) 坐标。注意:不会有两条鳄鱼待在同一个点上。
输出
如果007有可能逃脱,就在一行中输出"Yes",否则输出"No"。
样例输入
样例#1:
14 20 25 -15 -25 28 8 49 29 15 -35 -2 5 28 27 -29 -8 -28 -20 -35 -25 -20 -13 29 -30 15 -35 40 12 12
样例#2:
4 13 -12 12 12 12 -12 -12 12 -12
样例输出
样例#1:
Yes
样例#2:
No
#include <iostream>
#include <vector>
#include <cmath>
using namespace std;
const int N = 110;
struct Node
{
int x, y;
};
Node v[N];
int n, d;
bool st[N], flag = false;
vector<int> firststep;
bool check(int a, int b) {
int dx, dy;
dx = pow(v[a].x - v[b].x, 2);
dy = pow(v[a].y - v[b].y, 2);
if (dx + dy <= d * d)
return true;
return false;
}
void DFS(int x) {
st[x] = true;
if (v[x].x - d <= -50 || v[x].x + d >= 50 || v[x].y - d <= -50 || v[x].y + d >= 50) {
flag = true;
return;
}
for (int i = 0; i < n; i++)
{
if (!st[i] && check(x, i))
DFS(i);
}
}
int main() {
cin >> n >> d;
for (int i = 0; i < n; i++) {
int a, b;
cin >> a >> b;
v[i].x = a, v[i].y = b;
if (pow(a, 2) + pow(b, 2) <= pow(7.5 + d, 2))
firststep.push_back(i);
}
if (d >= 50) {
puts("Yes");
return 0;
}
for (int i = 0; i < firststep.size(); i++)
DFS(firststep[i]);
if (flag) puts("Yes");
else puts("No");
return 0;
}//参考代码2
#include <iostream>
#include <vector>
#include <cmath>
#include <queue>
using namespace std;
// 计算两点之间的距离
double distance(double x1, double y1, double x2, double y2) {
return sqrt((x2 - x1) * (x2 - x1) + (y2 - y1) * (y2 - y1));
}
// 判断是否能从当前位置跳到岸边
bool canEscape(double x, double y, double D) {
return abs(x) >= 50 - D || abs(y) >= 50 - D;
}
// 判断能否从一个鳄鱼位置跳到另一个鳄鱼位置或岸边
bool canReach(double x1, double y1, double x2, double y2, double D) {
return distance(x1, y1, x2, y2) <= D;
}
// 广度优先搜索判断是否能逃出生天
bool bfs(int N, double D, vector<pair<double, double>>& crocodiles) {
vector<bool> visited(N, false);
queue<int> q;
// 先将起始位置(小岛)加入队列
q.push(0);
while (!q.empty()) {
int cur = q.front();
q.pop();
if (!visited[cur]) {
visited[cur] = true;
// 判断当前位置能否直接跳到岸边
if (cur == 0) {
for (int i = 0; i < N; ++i) {
if (canReach(0, 0, crocodiles[i].first, crocodiles[i].second, D)) {
q.push(i);
}
}
} else {
if (canEscape(crocodiles[cur].first, crocodiles[cur].second, D)) {
return true;
}
// 尝试跳到其他鳄鱼位置
for (int i = 0; i < N; ++i) {
if (!visited[i] && canReach(crocodiles[cur].first, crocodiles[cur].second, crocodiles[i].first, crocodiles[i].second, D)) {
q.push(i);
}
}
}
}
}
return false;
}
int main() {
int N;
double D;
cin >> N >> D;
vector<pair<double, double>> crocodiles(N);
for (int i = 0; i < N; ++i) {
cin >> crocodiles[i].first >> crocodiles[i].second;
}
if (bfs(N, D, crocodiles)) {
cout << "Yes" << endl;
} else {
cout << "No" << endl;
}
return 0;
}月饼
月饼是中国人在中秋佳节时吃的一种传统食品,不同地区有许多不同风味的月饼。现给定所有种类月饼的库存量、总售价、以及市场的最大需求量,请你计算可以获得的最大收益是多少。
注意:销售时允许取出一部分库存。样例给出的情形是这样的:假如我们有 3 种月饼,其库存量分别为 18、15、10 万吨,总售价分别为 75、72、45 亿元。如果市场的最大需求量只有 20 万吨,那么我们最大收益策略应该是卖出全部 15 万吨第 2 种月饼、以及 5 万吨第 3 种月饼,获得 72 + 45/2 = 94.5(亿元)。
时间限制:5000
内存限制:262144
输入
每个输入包含一个测试用例。每个测试用例先给出一个不超过 1000 的正整数 N 表示月饼的种类数、以及不超过 500(以万吨为单位)的正整数 D 表示市场最大需求量。随后一行给出 N 个正数表示每种月饼的库存量(以万吨为单位);最后一行给出 N 个正数表示每种月饼的总售价(以亿元为单位)。数字间以空格分隔。
输出
对每组测试用例,在一行中输出最大收益,以亿元为单位并精确到小数点后 2 位。
样例输入
3 20 18 15 10 75 72 45
样例输出
94.50
#include<bits/stdc++.h>
using namespace std;
int n,m;
double a[1005];
double v[1005];
double sum[1005];
double ans;
double dp[1005];
int main()
{
cin>>n>>m;
for(int i=1;i<=n;i++)
{
cin>>a[i];//这是数量
}
for(int i=1;i<=n;i++)
{
cin>>sum[i];
v[i]=sum[i]/a[i];//这是价值
}
//价格为1
//多重背包模板
for(int i=1;i<=n;i++)
{
for(int j=m;j>=0;j--)
{
for(int k=1;k<=a[i];k++)
{
if(j>=k)
{
dp[j]=max(dp[j],dp[j-k]+v[i]*k);
}
}
}
}
//记得输出的时候要保留两位小数
cout<<fixed<<setprecision(2)<<dp[m]<<endl;
return 0;
}整数分解
正整数 N 的 K-P 分解是指将 N 写成 K 个正整数的 P 次方的和。本题就请你对任意给定的正整数 N、K、P,写出 N 的 K-P 分解。
时间限制:8000
内存限制:262144
输入
输入在一行给出 3 个正整数 N (≤ 400)、K (≤ N)、P (1 < P ≤ 7),以空格分隔。
输出
如果存在解,则按下列格式输出: N = n[1]^P + ... n[K]^P 其中 n[i] (i = 1, ..., K) 是第 i 个分解因子。所有的分解因子要按非增顺序输出。 注意:解可能是不唯一的。例如 169 的 5-2 分解就存在 9 个解,如 12^2 + 4^2 + 2^2 + 2^2 + 1^2 或 11^2 + 6^2 + 2^2 + 2^2 + 2^2 等等。你必须输出分解因子和最大的那个解。如果还不唯一,则输出具有最大的分解因子序列的解 —— 我们称序列 { a1, a2, … , aK } 比序列 { b1, b2, … , bK } 大,如果存在 1 ≤ L ≤ K 使得 ai=bi 对于 i < L 成立,并且有 aL > bL。 如果解不存在,则输出 `Impossible`。
样例输入
样例#1:
169 5 2
样例#2:
169 167 3
样例输出
样例#1:
169 = 6^2 + 6^2 + 6^2 + 6^2 + 5^2
样例#2:
Impossible
#include<bits/stdc++.h>
using namespace std;
const int N = 410;
int n, k, p;
int f[21][N][N];
//计算a的b次方
int power(int a, int b)
{
int res = 1;
for (int i = 0; i < b; i++) res *= a;
return res;
}
int main()
{
cin >> n >> k >> p;
//初始化
memset(f, -0x3f, sizeof f);
f[0][0][0] = 0;
//开始dp
int m;
for (m = 1;; m++) //从1开始向后枚举
{
int v = power(m, p); //计算m的p次方
if (v > n) break; //如果当前枚举的数已经超过n,则dp结束
//更新数据
for (int i = 0; i <= n; i++)
for (int j = 0; j <= k; j++)
{
//不选当前数
f[m][i][j] = f[m - 1][i][j];
//选当前数
if (i >= v && j) f[m][i][j] = max(f[m][i][j], f[m][i - v][j - 1] + m);
}
}
m--;
//从得到的集合中开始拆分出答案
if (f[m][n][k] < 0) puts("Impossible");
else
{
printf("%d = ", n);
bool is_first = true;
while (m)
{
int v = power(m, p);
//判断答案集合中是否有m
while (n >= v && k && f[m][n - v][k - 1] + m == f[m][n][k])
{
if (is_first) is_first = false;
else printf(" + ");
printf("%d^%d", m, p);
n -= v, k--;
}
m--;
}
}
return 0;
}森森快递
森森开了一家快递公司,叫森森快递。因为公司刚刚开张,所以业务路线很简单,可以认为是一条直线上的N个城市,这些城市从左到右依次从0到(N-1)编号。由于道路限制,第i号城市(i=0, … , N-2)与第(i+1)号城市中间往返的运输货物重量在同一时刻不能超过Ci公斤。
公司开张后很快接到了Q张订单,其中j张订单描述了某些指定的货物要从Sj号城市运输到Tj号城市。这里我们简单地假设所有货物都有无限货源,森森会不定时地挑选其中一部分货物进行运输。安全起见,这些货物不会在中途卸货。
为了让公司整体效益更佳,森森想知道如何安排订单的运输,能使得运输的货物重量最大且符合道路的限制?要注意的是,发货时间有可能是任何时刻,所以我们安排订单的时候,必须保证共用同一条道路的所有货车的总重量不超载。例如我们安排1号城市到4号城市以及2号城市到4号城市两张订单的运输,则这两张订单的运输同时受2-3以及3-4两条道路的限制,因为两张订单的货物可能会同时在这些道路上运输。
时间限制:5000
内存限制:262144
输入
输入在第一行给出两个正整数N和Q(2 ≤ N ≤ 105, 1 ≤ Q ≤ 105),表示总共的城市数以及订单数量。 第二行给出(N-1)个数,顺次表示相邻两城市间的道路允许的最大运货重量Ci(i=0, … , N-2)。题目保证每个Ci是不超过231的非负整数。 接下来Q行,每行给出一张订单的起始及终止运输城市编号。题目保证所有编号合法,并且不存在起点和终点重合的情况。
输出
在一行中输出可运输货物的最大重量。
样例输入
10 6 0 7 8 5 2 3 1 9 10 0 9 1 8 2 7 6 3 4 5 4 2
样例输出
7
提示
样例提示: 我们选择执行最后两张订单,即把5公斤货从城市4运到城市2,并且把2公斤货从城市4运到城市5,就可以得到最大运输量7公斤。
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#define inf 0x3f3f3f3f3f
using namespace std;
typedef pair<int,int> pa;
typedef long long ll;
int n,q;
ll ans;
int v[100005];
pa p[100005];
int tree[400005],lazy[400005];
bool cmp(const pa &a,const pa &b) {
if(a.second == b.second) return a.first < b.first;
return a.second < b.second;
}
void build(int l,int r,int t) {
lazy[t] = 0;
if(l == r) tree[t] = v[l];
else {
int mid = (l + r) >> 1;
build(l,mid,t << 1);
build(mid + 1,r,t << 1 | 1);
tree[t] = min(tree[t << 1],tree[t << 1 | 1]);
}
}
void pushdown(int t) {
if(lazy[t] == 0) return;
lazy[t << 1] += lazy[t];
lazy[t << 1 | 1] += lazy[t];
tree[t << 1] -= lazy[t];
tree[t << 1 | 1] -= lazy[t];
lazy[t] = 0;
}
void update(int l,int r,int t,int L,int R,int d) {
if(l >= L && r <= R) tree[t] -= d,lazy[t] += d;
else {
pushdown(t);
int mid = (l + r) >> 1;
if(mid >= L) update(l,mid,t << 1,L,R,d);
if(mid < R) update(mid + 1,r,t << 1 | 1,L,R,d);
tree[t] = min(tree[t << 1],tree[t << 1 | 1]);
}
}
ll query(int l,int r,int t,int L,int R) {
if(l >= L && r <= R) return tree[t];
if(l > R || r < L) return inf;
int mid = (l + r) >> 1;
ll d = inf;
pushdown(t);
if(mid >= L) d = min(d,query(l,mid,t << 1,L,R));
if(mid < R) d = min(d,query(mid + 1,r,t << 1 | 1,L,R));
tree[t] = min(tree[t << 1],tree[t << 1 | 1]);
return d;
}
int main() {
scanf("%d%d",&n,&q);
for(int i = 0;i < n - 1;i ++) {
scanf("%d",&v[i]);
}
build(0,n - 2,1);
for(int i = 0;i < q;i ++) {
scanf("%d%d",&p[i].first,&p[i].second);
if(p[i].first > p[i].second) swap(p[i].first,p[i].second);
p[i].second --;
}
sort(p,p + q,cmp);
for(int i = 0;i < q;i ++) {
ll d = query(0,n - 2,1,p[i].first,p[i].second);
ans += d;
update(0,n - 2,1,p[i].first,p[i].second,d);
}
printf("%lld",ans);
}能量节点
题目描述
数轴上分布着 n 个能量节点,第 i 个节点的坐标为 xi 。
当两个节点的距离小于等于 d 时,会产生能量共鸣。
求一共有多少组节点会发生能量共鸣。
输入格式
第一行,两个整数表示 n 与 d。
第二行,n 个整数,表示 x1,x2,…,xn 。
输出格式
单个整数:表示有多少对点可以会产生能量共鸣。
输入样例
4 25 30 40 10 20
输出样例
5
说明提示
1≤n≤100,000,
1≤d≤1,000,000,000,
1≤xi≤1,000,000,000。
限制
时间限制:1000ms
内存限制:256MiB
#include<iostream>
#include<algorithm>
int main()
{
int n, d;
std::cin >> n >> d;
int a[100005];
for(int i = 1;i <= n; ++i)
std::cin >> a[i];
std::sort(a + 1, a + n + 1);
long long pair = 0;
for(int i = 1, j = 1; i <= n; ++i)
{
while(a[j] - a[i] <= d && j <= n)
j++;
pair += j - i - 1;
}
std::cout << pair;
}刷任务
题目描述
一共有 n 个小任务,第 i 个任务会消耗 ai 点体力、bi 点心神。
你可以自由安排任务的完成顺序,逐个依次做完任务。
当累计消耗的体力总和超过 xx,或是 累计消耗的心神总和超过 y 时,会立刻停下无法继续做事。
求:在运气最差、顺序最不利的情况下,你最少会完成多少个任务就被迫停止。
输入格式
第一行,三个整数表示 n, x, y
第二行,n 个整数表示 a1,a2,…,an
第三行,n 个整数表示 b1,b2,…,bn
输出格式
输出一个整数,表示最少完成的任务数量。
输入样例#1
4 7 18 2 3 5 1 8 8 1 4
输出样例#1
2
输入样例#2
8 30 30 1 2 3 4 5 6 7 8 8 7 6 5 4 3 2 1
输出样例#2
6
说明提示
1≤n≤2×105
1≤x,y≤2×1014
1≤ai,bi≤109
限制
时间限制:1000ms
内存限制:256MiB
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
using ll = long long;
struct Task {
ll a, b;
};
int n;
ll X, Y;
vector<Task> t, ta, tb;
vector<ll> sa, sb;
// 按a升序
bool cmpA(const Task &x, const Task &y) {
return x.a < y.a;
}
// 按b升序
bool cmpB(const Task &x, const Task &y) {
return x.b < y.b;
}
bool check(int k) {
if (k == 0) return false;
// a排序后缀和
int pos = n - k;
ll sumA = sa[pos];
ll minA = ta[pos].a;
bool cond1 = (sumA - minA) <= X;
// b排序后缀和
ll sumB = 0;
vector<ll> sbb(n + 1, 0);
for (int i = n - 1; i >= 0; i--) sbb[i] = sbb[i + 1] + tb[i].b;
pos = n - k;
sumB = sbb[pos];
ll minB = tb[pos].b;
bool cond2 = (sumB - minB) <= Y;
bool cond3 = (sumA > X) || (sumB > Y);
return cond1 && cond2 && cond3;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> n >> X >> Y;
t.resize(n);
for (int i = 0; i < n; ++i) cin >> t[i].a;
for (int i = 0; i < n; ++i) cin >> t[i].b;
ta = t; tb = t;
sort(ta.begin(), ta.end(), cmpA);
sort(tb.begin(), tb.end(), cmpB);
// 预处理a后缀和
sa.assign(n + 1, 0);
sb.assign(n + 1, 0);
for (int i = n - 1; i >= 0; --i) {
sa[i] = sa[i + 1] + ta[i].a;
}
int l = 1, r = n, ans = n;
while (l <= r) {
int mid = (l + r) / 2;
if (check(mid)) {
ans = mid;
r = mid - 1;
} else {
l = mid + 1;
}
}
cout << ans << endl;
return 0;
}字符串的不同字串
题目描述
给定一个由小写英文字母组成的字符串 s。请问 s的不同非空子串有多少种?
子串是指字符串中连续的一段字符。例如,xxx 是 yxxxy 的子串,但不是 xxyxx 的子串。
输入
输入一行,包含一个字符串 s。
输出
输出一个整数,表示 s的不同非空子串的数量。
数据范围
s仅由小写英文字母组成。
1≤∣s∣≤100,其中 ∣s∣表示字符串的长度。
输入样例1
aababc
输出样例1
17
输入样例2
abracadabra
输出样例2
54
#include <bits/stdc++.h>
using namespace std;
int main() {
string s;
cin >> s;
int n = s.length();
set<string> st; //使用set保存子串去重
for (int i = 0; i < n; i++) { //枚举所有子串
string sub = "";
for (int j = i; j < n; j++) {
sub += s[j];
st.insert(sub);
}
}
cout << st.size() << endl;
}坐标选点
题目描述
修建了一条长度为 m 公里的铁路,起点和终点已经建有火车站。铁路沿线有 n 座城市(城市不位于起点或终点),第 i 座城市到铁路起点的距离为 ai 公里。
现在计划在这 n 座城市中选择 c 座修建火车站,使得所有火车站(包括起点和终点的火车站)之间的最小相邻距离尽可能大。请你计算这个最小相邻距离的最大可能值。
输入
第一行包含三个正整数n、c、m,分别表示城市数量、计划修建的火车站数量以及铁路总长度。
第二行包含n个正整数a1,a2,...,an,表示每座城市到铁路起点的距离。
输出
输出一个整数,表示最小相邻距离的最大可能值。
数据范围
1≤c≤n≤10^6,1≤ai<m≤10^9,输入中的所有数值均为整数。
输入样例1
5 3 10 1 2 8 4 9
输出样例1
2
#include <bits/stdc++.h>
using namespace std;
int n, c, m, a[1000000] ;
bool check(int minDist) {
int count = 0; // 已经选择的中间火车站数量
int lastPos = 0; // 上一个火车站的位置(起点)
for (int i = 0; i < n; i++) {
if (a[i] - lastPos >= minDist) {
count++;
lastPos = a[i];
if (count >= c) break; // 已经选够
}
}
// 检查最后一个火车站到终点的距离是否满足
if (count >= c && (m - lastPos) >= minDist) {
return true;
}
return false;
}
int main() {
cin >> n >> c >> m;
for (int i = 0; i < n; i++) {
cin >> a[i];
}
sort(a, a+n);
int low = 1, high = m, ans = 0;
while (low <= high) {
int mid = (low + high) / 2;
if (check(mid)) {
ans = mid;
low = mid + 1; // 尝试更大的距离
} else {
high = mid - 1;
}
}
cout << ans << endl;
return 0;
}国际象棋
题目描述
有一个 N x N 的巨大棋盘,包含 N^2 个格子。棋盘的行和列都从 1 到 N 编号,格子(i, j) 表示第 i 行第 j 列的格子。
目前棋盘上已经放置了 M 个马,第 k 只马位于格子 (ak, bk)。每个格子保证最多只能有一个棋子。
请统计,这个棋盘上有多少空格子,不会被任意一只马吃掉。
如果一只马在 (i, j),那么它可以攻击以下 8 个位置(这些位置需要在棋盘边界范围内):
(1)(i + 2, j + 1)
(2)(i + 1, j + 2)
(3)(i - 1, j + 2)
(4)(i - 2, j + 1)
(5)(i - 2, j - 1)
(6)(i - 1, j - 2)
(7)(i + 1, j - 2)
(8)(i + 2, j -1)
输入格式
第一行包含两个整数 N 和 M,分别表示棋盘大小和已有棋子数量。
接下来 M 行,每行包含两个整数 ak 和 bk,表示第 k 个棋子的位置。
输出格式
输出一个整数,表示可以安全放置棋子的空格子数量。
输入样例1
2 1 1 1
输出样例1
3
输入样例2
3 7 3 2 1 3 2 3 3 3 3 1 2 1 1 1
输出样例2
1
数据范围
1≤N≤10^9,1≤M≤2×10^5,1<=ak、bk<=N,所有棋子位置互不相同,输入均为整数。
#include <bits/stdc++.h>
using namespace std;
vector<pair<int, int>> horse;
vector<pair<int, int>> pos;
int dx[8] = {2, 1, -1, -2, -2, -1, 1, 2};
int dy[8] = {1, 2, 2, 1, -1, -2, -2, -1};
int main() {
int n, m, coun = 0;
cin >> n >> m;
//由于N的范围较大,不可能使用N*N的数组
//这里计算马能攻击的格子数x, 安全位置则是N*N-x-m
for(int i=0; i<m; i++) {
int x, y, ax, ay;
cin >> x >> y;
horse.push_back(make_pair(x, y));
for(int j=0; j<8; j++) {
ax = x+dx[j];
ay = y+dy[j];
if(ax>=1 && ax<=n && ay>=1 && ay<=n) {
if(find(pos.begin(), pos.end(), make_pair(ax, ay))==pos.end()) {
pos.push_back(make_pair(ax, ay));
}
}
}
}
//统计pos位置包含的马
int k = 0;
vector<pair<int, int>>::iterator it;
for(it=pos.begin();it!=pos.end();it++) {
if(find(horse.begin(), horse.end(), *it) != horse.end())
k++;
}
long long num = (long long)n*n - (m - k);
num -=pos.size();
cout << num;
return 0;
}