A
爬山
Time Limit: 3000/1000 MS (Java/Others) Memory Limit: 65536/65536 K (Java/Others)
Total Submission(s): 0 Accepted Submission(s): 0
Problem Description
小Z准备去爬山，在他的面前有N座山，每座山都有对应的高度。他想选择两座高度差最小的山进行攀爬。但由于好多山之间的高度差可能是相同的，所以他需要你告诉他高度差最小的两座山的高度差是多少以及有多少种不同的选取方式(选取山A、B和选取山B、A视为同一种选取方式)。
Input
输入一个T，代表数据的组数。（T<=10）
每组数据包含一个N，代表有多少座山。（2<=N<=100,000）
接下来一行包括N个数，分别表示每座山的高度x(1<=x<=1000,000,000)。
Output
对于每组测试样例，输出一行，包含两个整数，代表两座山最小的高度,以及有多少种不同的方式选取两座山。两个数之间用一个空格隔开,每个测试样例占一行。
Sample Input
2 5 1 2 5 4 3 4 3 3 3 10
Sample Output
1 4 0 3
Hint
测试样例包含2组样例 第一组样例有5座山，高度分别为1,2,5,4,3,所以高度差最小是1,有4种不同的选取方式， 分别为选取第一座山和第二座山、选取第二座山和第五座山、选取第四座山和第五座山、选取第三座山和第四座山。 第二组样例有4座山，高度分别为3,3,3,10,所以高度差最小是0,有3种不同的选取方式， 分别为选取第一座山和第二座山、选取第二座山和第三座山、选取第一座山和第三座山。
解题报告：
记得开longlong就好。。
AC代码：
#include<iostream>
#include<string>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<cstring>
#include<queue>
#include<stack>
#include<map>
#include<string.h>
#define ll long long
#define inf 1e7
using namespace std;
ll a[200000];
map<ll,ll> mp;
int main()
{
int t;
scanf("%d",&t);
while(t--)
{
mp.clear();
int n;
scanf("%d",&n);
for(int i=0;i<n;i++)
{
scanf("%lld",&a[i]);
mp[a[i]]++;
}
sort(a,a+n);
ll minn=2000000000;
for(int i=n-1;i>=1;i--)
{
minn=min(minn,a[i]-a[i-1]);
}
ll ans=0;
if(minn==0)
for(int i=n-1;i>=1;i--)
{
if(mp[a[i]]>1)
{
ll te=mp[a[i]];
ans+=te*(te-1)/2;
mp[a[i]]=1;
}
}
else
for(int i=n-1;i>=1;i--)
{
if(minn==a[i]-a[i-1])
{
ans+=mp[a[i]]*mp[a[i-1]];
}
}
printf("%lld %lld\n",minn,ans);
}
return 0;
} B
寻找消失的纸牌
Time Limit: 3000/1000 MS (Java/Others) Memory Limit: 65536/65536 K (Java/Others)
Total Submission(s): 0 Accepted Submission(s): 0
Problem Description
在一个无聊的假期，小Z和他的伙伴准备斗地主。纸牌拿出来除去大小王发现只有51张(实际应该有52张)，小z想让你帮忙找出消失的那张纸牌。纸牌的花色分别对应为A、B、C、D，纸牌的点数对应为1、2、3、4、5、6、7、8、9、10、J、Q、K。例如红桃10对应为C10，梅花K对应为BK。
Input
第一行为一个整数T，代表有T组样例。（T<=52)
每组数据中由51张牌组成，纸牌之间以空格隔开，牌顺序打乱。每组数据占一行。
Output
对于每个测试样例，输出消失的纸牌。每个测试样例占一行。
Sample Input
2
A1 A2 A3 A4 A5 A6 A7 A8 A9 A10 AJ AQ B1 B2 B3 B4 B5 B6 B7 B8 B9 B10 BJ BQ BK C1 C2 C3 C4 C5 C6 C7 C8 C9 C10 CJ CQ CK D1 D2 D3 D4 D5 D6 D7 D8 D9 D10 DJ DQ DK
A1 A2 A3 A4 A5 A6 A7 A8 A9 A10 AJ AQ AK B1 B2 B3 B4 B5 B6 B7 B8 B9 B10 BJ BQ BK C1 C2 C3 C4 C5 C6 C8 C9 C10 CJ CQ CK D1 D2 D3 D4 D5 D6 D7 D8 D9 D10 DJ DQ DK
Sample Output
AK C7
解题报告：
set一发。
AC代码：
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<queue>
#include<map>
#include<vector>
#include<set>
#include<string>
#include<cmath>
#include<cstring>
#define ll long long
#define pb push_back
#define pm make_pair
#define fi first
#define se second
using namespace std;
set<string> ss;
int main()
{
char str[5];
int t;
cin>>t;
while(t--) {
ss.clear();
ss.insert("A1");ss.insert("A2");ss.insert("A3");ss.insert("A4");ss.insert("A5");ss.insert("A6");ss.insert("A7");ss.insert("A8");ss.insert("A9");ss.insert("A10");ss.insert("AJ");ss.insert("AQ");ss.insert("B1");ss.insert("B2");ss.insert("B3");ss.insert("B4");ss.insert("B5");ss.insert("B6");ss.insert("B7");ss.insert("B8");ss.insert("B9");ss.insert("B10");ss.insert("BJ");ss.insert("BQ");ss.insert("BK");ss.insert("C1");ss.insert("C2");ss.insert("C3");ss.insert("C4");ss.insert("C5");ss.insert("C6");ss.insert("C7");ss.insert("C8");ss.insert("C9");ss.insert("C10");ss.insert("CJ");ss.insert("CQ");ss.insert("CK");ss.insert("D1");ss.insert("D2");ss.insert("D3");ss.insert("D4");ss.insert("D5");ss.insert("D6");ss.insert("D7");ss.insert("D8");ss.insert("D9");ss.insert("D10");ss.insert("DJ");ss.insert("DQ");ss.insert("DK");
ss.insert("AK");
for(int i = 1; i<=51; i++) {
scanf("%s",str);
ss.erase(str);
}
cout << *ss.begin()<<endl;
}
// ss.insert("")
return 0 ;
} C
球球大作战
Time Limit: 3000/1000 MS (Java/Others) Memory Limit: 65536/65536 K (Java/Others)
Total Submission(s): 0 Accepted Submission(s): 0
Problem Description
小Z最近迷上了球球大作战，他准备出一个与球球大作战相似的题目来考考大家。现在有n个球依次排列在一条直线上，每个球有其对应的体积。每次合并操作可以将任意相邻两个球合并为一个球，合并之后的球的体积为这两相邻球体积之和。现在有m次合并，经过这m次合并之后，希望剩下球中体积的最小值能够最大(采用最佳合并策略)。
Input
输入一个T，代表数据的组数。（T<=10）
第二行包含两个正整数N,M，表示N个球，M次合并机会。
接下来一行为n个正整数x[1], x[2], … ,x[n]，其中x[i]表示编号为i的球的体积。
数据范围：1≤M<N≤100000，1≤x[i]≤100000。
Output
对于每个测试样例，输出一行，包含一个整数，m次合并之后的剩下的球的体积的最小值最大是多少。每个测试样例占一行。
Sample Input
2 4 2 4 2 3 5 6 3 1 7 2 2 5 9
Sample Output
6 8 Hint： 第一组样例： 合并4、2得到{ 6 3 5 },合并3、5得到{ 6 8 }，最小值为6。 也可以这样进行合并，合并2、3得到{ 4 5 5 },合并4、5得到{ 9 5 }，最小值为5,但最小值小于上面的合并方案。 第二组样例： 合并1、7得到 { 8 2 2 5 9 }，合并2、2得到 { 8 4 5 9 }，合并4、5得到 { 8 9 9 }，最小值为8。
解题报告：
二分最小值然后遍历数组就好了，，复杂度o(nlogn)、
AC代码：
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<queue>
#include<map>
#include<vector>
#include<set>
#include<string>
#include<cmath>
#include<cstring>
#define ll long long
#define pb push_back
#define pm make_pair
#define fi first
#define se second
using namespace std;
const int MAX = 200000 + 5;
ll a[MAX],b[MAX],n,m;
bool ok(ll x) {
ll cnt = 0;
for(int i = 1; i<=n+1; i++) b[i] = a[i];
for(int i = 1; i<=n; i++) {
if(b[i] < x) {
b[i+1] = b[i]+b[i+1];
cnt++;
}
}
return cnt <= m;
}
int main()
{
int t;
cin>>t;
while(t--) {
ll sum = 0;
scanf("%lld%lld",&n,&m);
memset(a,0,sizeof a);
for(int i = 1; i<=n; i++) scanf("%lld",a+i),sum += a[i];
ll l = 0,r = sum;
ll mid = (l+r)>>1,ans = 0;
while(l<=r) {
mid=(l+r)>>1;
if(ok(mid)) {
ans = mid;l=mid+1;
}
else r=mid-1;
}
printf("%lld\n",ans);
}
return 0 ;
}
/*
1
6 3
1 7 2 2 5 9
*/ D
矩阵
Time Limit: 3000/1000 MS (Java/Others) Memory Limit: 65536/65536 K (Java/Others)
Total Submission(s): 0 Accepted Submission(s): 0
Problem Description
有一个二维矩阵，长和宽分别是N,M。矩阵上的每个点有两个状态(0,1)，问能不能找到一个K*K的子矩阵，子矩阵里面每个点的状态全为0？
Input
第一行为一个整数T，代表T组数据。（1=<T<=10)
第二行为三个整数N,M,K。（1<=N,M<=1000,1<=K<=min(N,M)）
接下来N行，每行有M个整数，代表矩阵上对应的点的状态，状态只有0,1两种。
Output
对于每个测试样例，输出一行，如果能找到子矩阵，输出"Yes"，否则输出"No"。每个测试样例占一行。
Sample Input
2 3 3 2 1 0 0 1 0 0 1 1 1 3 3 2 1 0 0 0 1 0 0 0 0
Sample Output
Yes No
解题报告：
裸的二维前缀和、、
AC代码：
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<queue>
#include<map>
#include<vector>
#include<set>
#include<string>
#include<cmath>
#include<cstring>
#define ll long long
#define pb push_back
#define pm make_pair
#define fi first
#define se second
using namespace std;
int a[1005][1005],n,m,k;
int sum[1005][1005];
int main()
{
int t;
cin>>t;
while(t--) {
scanf("%d%d%d",&n,&m,&k);
memset(a,0,sizeof a);
for(int i = 1; i<=n; i++) {
for(int j = 1; j<=m; j++) {
scanf("%d",&a[i][j]);
}
}
for(int i = 1; i<=n; i++) {
for(int j = 1; j<=m; j++) {
sum[i][j] = a[i][j]+sum[i-1][j]+sum[i][j-1]-sum[i-1][j-1];
}
}
int flag = 0;
for(int i = k; i<=n; i++) {
for(int j = k; j<=m; j++) {
if(sum[i][j] - sum[i][j-k] - sum[i-k][j] + sum[i-k][j-k] == 0) {
flag=1;break;
}
}
if(flag == 1) break;
}
if(flag) puts("Yes");
else puts("No");
}
return 0 ;
} E
序列专一
Time Limit: 3000/1000 MS (Java/Others) Memory Limit: 65536/65536 K (Java/Others)
Total Submission(s): 0 Accepted Submission(s): 0
Problem Description
小Z是一个专一的人，他希望能把一个序列里面的数也能够唯一(即元素之间各不相同)。因为序列刚开始可能会有重复的数，所以他需要进行一些操作。每次操作可从序列中取出两个数x,y，把max(x+y-1,max(x,y)-min(x,y)+2)放入序列中，再把x和y其中一个放入序列，丢弃另外一个。问至少需要操作多少次可以使序列里面的数各不相同。
Input
输入一个T，代表数据的组数。（T<=10）
每组数据包含一个N，代表这个序列有多少个数。（N<=100,000）
接下来一行包括N个数，分别表示序列中每个数的值x (1<=x<=100,000)。
Output
对于每个测试样例，输出一行，包含一个整数，代表至少需要操作多少次可以使序列里面的数各不相同。每个测试样例占一行。
Sample Input
3 5 1 2 3 4 5 6 2 2 3 3 4 5 4 2 2 2 2
Sample Output
0 2 3 Hint: 数据输入量较大，建议使用scanf，不要使用cin 第一组样例不需要操作。 第二组样例需要进行二次操作。第一次操作取出数2和5,丢弃2,放入5和6。第二次操作取出数3和5,丢弃3,放入5和7。最终的序列为2,3,4,5,6,7。 也可以这样对第二组样例进行操作。第一次操作取出数2和5,丢弃2,放入5和6。第二次操作取出数3和6,丢弃3,放入6和8。最终的序列为2,3,4,5,7,8。
解题报告：
这题需要分析题目给出的式子，，会发现：给出一对(x,y) 总会得到一个max(x,y)的数、、所以操作的时候我们从大到小操作就一定可以，所以这题就变成找不同数的个数的题目。。
AC代码：
#include<iostream>
#include<string>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<cstring>
#include<queue>
#include<stack>
#include<map>
#include<string.h>
#define ll long long
#define inf 1e7
using namespace std;
int a[100100];
map<int,int>mp;
int main()
{
int t;
scanf("%d",&t);
while(t--)
{
mp.clear();
priority_queue<int> que;
int n;
scanf("%d",&n);
for(int i=0;i<n;i++)
{
scanf("%d",&a[i]);
mp[a[i]]++;
}
int ans=0;
for(int i=0;i<n;i++)
{
if(mp[a[i]]>1)
{
ans+=mp[a[i]]-1;
mp[a[i]]=1;
}
}
printf("%d\n",ans);
}
return 0;
}
F
成语接龙
Time Limit: 3000/1000 MS (Java/Others) Memory Limit: 65536/65536 K (Java/Others)
Total Submission(s): 0 Accepted Submission(s): 0
Problem Description
小Z和大Z最近沉迷于成语接龙游戏，他们准备把成语接龙的规则修改一下。规则是这样的：有两个字符串，如果第一个字符串是第二个字符串的子串(也就是第一个字符串在第二个字符串中可以找到)，那么第一个字符串后面可以接第二个字符串。问题来了，现在有n个字符串，你可以把n个字符串的顺序进行重组，使得这n个字符串可以成语接龙，即第一个字符串后面可以接第二个字符串，第二个字符串后面可以接第三个字符串，......，第n-1个字符串后面可以跟第n个字符串。问你能不能把n个字符串顺序重组，满足这n个字符串可以成语接龙。
Input
第一行为一个整数T，代表有T组样例。（T<=10)
每组数据中：
第一行为一个整数N，表示有N个字符串。(N<=100)
接下来n行，每行一个字符串，每个字符串长度小于等于100。
Output
对于每组测试样例，如果这n个字符串顺序重排之后可以成语接龙，输出“Yes”，否则输出“No”。每个测试样例占一行。
Sample Input
3 5 Abcabc Abc Abca Abc A 2 ABAC ACB 2 ACDB ACB
Sample Output
Yes No No
Hint
第一组样例的成语接龙顺序可以为：A、Abc、Abc、Abca、Abcabc。
解题报告：
刚开始读错题意、、以为都从首字符开始，想想字典树？凉。直接o(n^2)找前驱？凉。WA两发之后、、老老实实分情况了。。
AC代码：
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<queue>
#include<map>
#include<vector>
#include<set>
#include<string>
#include<cmath>
#include<cstring>
#define ll long long
#define pb push_back
#define pm make_pair
#define fi first
#define se second
using namespace std;
char tmp[105];
struct Node {
char s[105];
int len;
} node[105];
char str[105][105];
bool cmp(Node a,Node b) {
if(a.len != b.len) return a.len < b.len;
return strcmp(a.s,b.s)<0;
}
int main()
{
int t;
cin>>t;
while(t--) {
int n;
cin>>n;
for(int i = 1; i<=n; i++) {
scanf("%s",tmp);
strcpy(node[i].s,tmp);
node[i].len = strlen(tmp);
}
if(n == 1) {
puts("Yes");continue;
}
sort(node+1,node+n+1,cmp);
int flag = 1;
for(int i = 1; i<n; i++) {
if(node[i].len == node[i+1].len) {
if(strcmp(node[i].s,node[i+1].s) != 0) flag = 0;break;
}
}
if(flag == 0) {
printf("No\n");
continue;
}
int top = 0;
for(int i = 1; i<n; i++) {
if(strcmp(node[i].s,node[i+1].s) != 0) {
top++;
strcpy(str[top],node[i].s);
}
}
if(strcmp(node[n].s,node[n-1].s) !=0) {
top++;
strcpy(str[top],node[n].s);
}
for(int i = 2; i<=top; i++) {
if(strstr(str[i],str[i-1]) == NULL) flag = 0;
}
if(flag) puts("Yes");
else puts("No");
}
return 0 ;
}
H
拯救柳下惠的气质
Time Limit: 3000/1000 MS (Java/Others) Memory Limit: 65536/65536 K (Java/Others)
Total Submission(s): 0 Accepted Submission(s): 0
Problem Description
柳下惠是一个卓越的探险家，有一次，柳下惠在外探险的过程中，在一个N*M的迷宫中迷路了，现在柳下惠处于迷宫中的(x,y)点，迷宫的入口在(1,1)点。只有你沿着最短的路径找到柳下惠，柳下惠才会跟你离开迷宫。在迷宫中，你可以走上下左右四个方向。问有多少种走法可以拯救柳下惠？答案对1000000007取模(每种走法只要有一步不同即视为不同)
Input
第一行有一个整数T，代表T组数据。（1<=T<=10）
每组数据的第一行有两个整数N,M代表迷宫的大小。（2<=N,M<=500）
接下来N行每行有M个字符。（包括.和*，.代表可以行走的路，*代表不可以行走的墙。）
每组数据的最后一行有两个整数x,y代表柳下惠现在的位置。(1<=x<=N,1<=y<=M)
（数据保证(1,1)和(x,y)的位置都是.，保证坐标(x,y)不等于(1,1)）
Output
对于每组数据，输出一行。
如果可以拯救柳下惠，输出可以拯救柳下惠的方案数,结果对1000000007取模。
如果不可以拯救柳下惠，输出-1。
Sample Input
2 2 2 .. .. 2 2 2 2 .* *. 2 2
Sample Output
2 -1
解题报告：
裸的最短路条数。。读题啊别忘了取模啊。。写着写着就忘了、、WA了三发有点伤。。细节还是要要注意、、
AC代码：
#include <iostream>
#include<cstring>
#include<cmath>
#include<cstdio>
#include<queue>
#define ll long long
using namespace std;
int r,c,qiux,qiuy;
const int INF = 0x3f3f3f3f;
const ll mod = 1000000007;
int dis[505][505];
char mm[505][505];
int maze[505][505];
ll ans[505][505];
bool vis[505][505];
int head[505];
int nx[4] = {0,1,0,-1};
int ny[4] = {1,0,-1,0};
struct Point {
int x,y;
int t;
bool operator<(const Point & b) const {
return t>b.t;
}
Point(){}
Point(int x,int y,int t):x(x),y(y),t(t) {}
}p;
void Dijkstra() {
dis[1][1] = 0;
ans[1][1] = 1;
int minw = INF;
priority_queue<Point > pq;
pq.push(Point(1,1,0));
while(!pq.empty()) {
int nxx,nyy;
//找点
Point cur = pq.top();pq.pop();
if(vis[cur.x][cur.y] == 1) continue;
vis[cur.x][cur.y] = 1;
for(int k = 0; k<4; k++) {
nxx = cur.x+nx[k];
nyy = cur.y+ny[k];
if(vis[nxx][nyy] == 1) continue;
if(nxx<1 || nxx>r || nyy<1 || nyy>c) continue;
int t = dis[cur.x][cur.y] + maze[nxx][nyy];
if(dis[nxx][nyy] > t) {
dis[nxx][nyy] = t;
ans[nxx][nyy] = ans[cur.x][cur.y]%mod;
pq.push(Point(nxx,nyy,dis[nxx][nyy]));
}
else if(dis[nxx][nyy] == t) {
ans[nxx][nyy] += ans[cur.x][cur.y];
ans[nxx][nyy] %= mod;
}
}
}
if(dis[qiux][qiuy] == INF) printf("-1\n");
else printf("%lld\n",ans[qiux][qiuy]%mod);
}
void init() {
memset(vis,0,sizeof(vis));
memset(ans,0,sizeof ans);
for(int i = 1; i<=r; i++) {
for(int j = 1; j<=c; j++) {
dis[i][j] = INF;
}
}
memset(maze,INF,sizeof(maze));
}
int main()
{
int t;
cin>>t;
while(t--) {
scanf("%d%d",&r,&c);
init();
for(int i = 1; i<=r; i++) {
scanf("%s",mm[i]+1);
}
scanf("%d%d",&qiux,&qiuy);
for(int i = 1; i<=r; i++) {
for(int j = 1; j<=c; j++) {
if(mm[i][j] == '.') maze[i][j] = 1;
}
}
Dijkstra() ;
}
return 0 ;
} G
三消游戏
Time Limit: 3000/1000 MS (Java/Others) Memory Limit: 65536/65536 K (Java/Others)
Total Submission(s): 0 Accepted Submission(s): 0
Problem Description
程序设计大赛这样的活动，报名选手自然少不了当当姐啦。作为太吾村里最聪明的同学，她不一会儿便完成了比赛中的所有题目。酷爱三消游戏的她顺手在草稿纸上发明了一种简单的数字三消游戏。
游戏中，每回合会给出一行n个数字，我们设其中第i个数字为a[i]。当当姐会把数字a[i]想象为一堆位于第i列的，高度为a[i]的积木（a[i]可以为0），而她每次操作，可以选择下标连续（如3,4,5）的三个非空积木堆，在每个积木堆上都各拿走一块积木。而如果再也找不到下标连续的三个非空积木堆，游戏便结束了。
当当姐想要知道的是，最少操作多少次，以及最多操作多少次，可以使得游戏结束呢？
注意，当一堆积木被消除为空时，所有积木的编号并不会发生改变。
Input
第一行为一个整数T，代表数据组数。
接下来，对于每组数据――
第一行两个整数n，表示积木的堆数。
第二行有n个用空格隔开的整数，其中第i个数字a[i]代表第i列的积木个数。
数据保证――
1 <= T <= 1000
0 <= a[i] <= 500
设a[1] + a[2] + ... + a[n] = m，有:
对于98%的数据，3 <= n <= 10 && 0 <= m <= 100
对于100%的数据，3 <= n <= 100 && 0 <= m <= 1000
Output
对于每组数据，输出两个数字。
该行有2个整数，分别表示当当姐游戏结束前最少的操作数和最多的操作数。
Sample Input
4 3 4 6 8 5 0 0 10 0 0 6 2 3 4 5 6 7 7 8 3 2 6 2 5 8
Sample Output
4 4 0 0 5 7 2 4
解题报告：
不太会啊、、想着线段树维护每个点的值，每次找2~n-1的最小值，减到0，顺便更新两侧的值 再找最小值，重复操作直到最小值为0？然后凉了、、第三个样例就不太行这样做。
AC代码：
暂无、、、
（ps：博客汇总有任何问题欢迎提出，一起讨论）
京公网安备 11010502036488号