T1
题目描述
给定一个n*m的矩阵,每次你可以选择前进一格或转弯(90度),求在不出这个矩阵的情况下遍历全部格点所需最少转弯次数。有多组数据
输入
第一行一个整数k,表示数据组数
以下k行,每行两个整数n,m,表示矩阵大小
输出
输出一个整数,即最少转弯次数
样例
样例输入1
2
1 10
10 1
样例输出1
0
0
样例输入2
3
1 1
3 3
3 4
样例输出2
0
4
4
样例输入3
2
5 8
6 4
样例输出3
8
6
解题思路
很明显,一直走s型或蛇型即可,答案即
代码
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<queue>
#include<cstdlib>
#include<vector>
using namespace std;
int k,n,m;
int main(){
//freopen("kosnja.in","r",stdin);
//freopen("kosnja.out","w",stdout);
scanf ("%d",&k);
while (k --){
scanf ("%d%d",&n,&m);
printf("%d
",(min(n,m) - 1) * 2);
}
}
T2
题目描述
Zig和Zag正在玩文字游戏。Zig说了一个字母,而Zag说了一个以该字母开头的单词。但是这个词需要出现在给出的单词列表中,并且被是相同首字母中使用的次数最少的单词。如果单词的选择不明确(即相同首字母中使用的次数最少的单词不止一个),那么Zag会选择字典序较小的字母。输入保证对于每个Zig的字母,都有可以选择的单词。
假设有一个由K个不同的单词组成的列表和一个Zig给出的N个字母组成的列表。编写一个程序,根据输入,输出Zag在游戏过程中说出的N个单词。
输入
输入格式: 第一行输入包含来自的正整数K(1≤K≤100 000)和N(1≤N≤100 000)。
以下K行是K个单词,由小写英文字母组成,不超过21个字母。
以下N行是Zig说的N个小写英文字母。
输出
N行,分别对应N个Zig的询问。
样例
样例输入1
4 5
zagreb
split
zadar
sisak
z
s
s
z
z
样例输出1
zadar
sisak
split
zagreb
zadar
样例输入2
5 3
london
rim
pariz
moskva
sarajevo
p
r
p
样例输出2
pariz
rim
pariz
样例输入3
1 3
zagreb
z
z
z
样例输出3
zagreb
zagreb
zagreb
解题思路
怎么说呢,其实就是一道模拟题,由于它查询首字母,那么你按首字母分开保存串,又要输出相等使用下字典序最小的那就可以排序。然后查一个输一个,输到底就直接回到第一个。
代码
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<queue>
#include<cstdlib>
#include<vector>
using namespace std;
struct node {
char c[25];
bool operator < (const node &a)const {
if (strcmp(c,a.c) <= 0)
return 1;
else
return 0;
}
}s[100005];
int k,n,pos[30],len[30],len1[30];
char c;
int main(){
//freopen("zigzag.in","r",stdin);
//freopen("zigzag.out","w",stdout);
scanf ("%d%d",&k,&n);
for (int i = 1;i <= k;i ++)
scanf ("%s",s[i].c);
sort(s + 1,s + 1 + k);
for (int i = 1;i <= k;i ++){
if (s[i].c[0] != s[i - 1].c[0])
pos[s[i].c[0] - 'a'] = i;
len[s[i].c[0] - 'a'] ++;
}
for (int i = 0;i <= 25;i ++)
len1[i] = pos[i];
while (n --){
scanf ("
");
scanf ("%c",&c);
int t = c - 'a';
printf("%s
",s[len1[t]].c);
len1[t] ++;
if (len1[t] - pos[t] == len[t])
len1[t] = pos[t];
}
}
T3(换了题QAQ)
题目描述
有n名同学要乘坐摆渡车从人大附中前往人民大学,第i位同学在第ti分钟去等车。只有一辆摆渡车在工作,但摆渡车容量可以视为无限大。摆渡车从人大附中出发、把车上的同学送到人民大学、再回到人大附中(去接其他同学),这样往返一趟总共花费m分钟(同学上下车时间忽略不计)。摆渡车要将所有同学都送到人民大学。 凯凯很好奇,如果他能任意安排摆渡车出发的时间,那么这些同学的等车时间之和最小为多少呢? 注意:摆渡车回到人大附中后可以即刻出发。
输入
第一行包含两个正整数n,m,以一个空格分开,分别代表等车人数和摆渡车往返一趟的时间。 第二行包含n个正整数,相邻两数之间以一个空格分隔,第i个非负整数ti代表第i个同学到达车站的时刻。
输出
输出一行,一个整数,表示所有同学等车时间之和的最小值(单位:分钟)。
样例
【样例输入1】
5 1
3 4 4 3 5
【样例输出1】
0
【样例输入2】
5 5
11 13 1 5 5
【样例输出2】
4
解题思路
原题NOIP2018PJ T3 摆渡车,虽然打过一次,但忘了,主要就是DP不知道该如何定义。
这次换了一个新的高端操作。
为何此题难搞,关键在于它不好转移。
首先,人的编号,我们肯定要搞到DP中去。
然后,我们围绕这一个i号的人,必须要再定义东西,与它,与答案有关的,就只能是它等待的时间。那么,
表示第i个人等待了j分钟的最小花费(注:可能已经上车但没走)
这便是一个最简陋的dp,看起来是四重循环,好像要炸。
肯定,k,l,i必须要枚举,但j却是可以算出来,既然在k号人时等了l分钟就走了那么再过m分钟车就回来了,减去i号人到达的时间就算了出来。还有一个问题,就是j可能为负,表示车在等人,我们就弄0就好。即
cost 又该如何算呢,首先,肯定要有j,中间这一段,有i - k个人在等车,等的时间呢,都包含i等的时间。所以需要(i - k) + j这一部分。
那么之前的等待时间呢,我们就需要另外取一个数组表示i这个人到一直到j这一个人到,中间一共的等待时间。
预处理出来即可。
然后处理下边界,可以打了。
代码
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<queue>
#include<cstdlib>
#include<vector>
#include<ctime>
using namespace std;
int n,m,t[1005],dp[505][205],s[505][505];
int main(){
freopen("bus.in","r",stdin);
freopen("bus.out","w",stdout);
scanf ("%d%d",&n,&m);
if (m == 1){
printf("0
");
return 0;
}
for (int i = 1;i <= n;i ++)
scanf ("%d",&t[i]);
sort(t + 1,t + 1 + n);
for (int i = 1;i <= n;i ++){
for (int j = 1;j < i ;j ++){
for (int k = j;k <= i;k ++)
s[j][i] += t[i] - t[k];
}
}
t[0] = -0x3f3f3f3f;
memset(dp,0x3f,sizeof(dp));
for (int i = 0;i <= m;i ++){
dp[0][i] = 0;
dp[1][i] = i;
}
for (int i = 2;i <= n;i ++){
for (int j = 0;j < i;j ++){
for (int k = 0;k <= m;k ++){
int w = t[j] + k + m - t[i];
if (w < 0)
dp[i][0] = min(dp[i][0],dp[j][k] + s[j + 1][i]);
else
dp[i][w] = min(dp[i][w],dp[j][k] + s[j + 1][i] + (i - j) * w);
}
}
}
int ans = 0x3f3f3f3f;
for (int i = 0;i <= m;i ++)
ans = min(ans,dp[n][i]);
printf("%d",ans);
}
T4
题目描述
游戏世界中有N个楼从左到右排列,从左到右编号为1到N,第i幢楼的高度为Hi,楼上的金币数为Gi,游戏可以从任意一个楼开始且包涵几步。每一步玩家可以从当前位置向右跳(可以跳过一些楼)但必须跳到不低于当前楼的高度的楼上。他到了楼上后,可以得到楼上的金币。他可以在跳任意步(可以是零步)后结束游戏,但是要保证收到的金币数要大于等于K,现在想知道共有多少不同的种方案满足游戏。两个方案不同是指至少有一个楼不一样的方案。
输入
第一行两个数N (1 ≤ N ≤ 40) and K (1 ≤ K ≤ 4·10^10 )
接下来N行,每行两个正整数,第i行用Hi和Gi表示第i个楼的高度和上面的金币。 (1 ≤ Hi, Gi ≤ 109 )
输出
一行一个数,表示方案总数。
样例
样例输入1
4 6
2 1
6 3
7 2
5 6
样例输出1
3
样例输入2
2 7
4 6
3 5
样例输出2
0
样例输入3
4 15
5 5
5 12
6 10
2 1
样例输出3
4
解题思路
看到这道题,一开始想dp,后面发现不对,立马搜索,2^20虚都不虚。然而没开LL
可以打搜索剪枝,但我真的想不到怎么剪,有大佬知道可以评论告诉一下。
正解折半搜索,把搜到的所有的情况全部储存(真暴力)。
再枚举啊,尺取啊,操作一下即可。
代码
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<queue>
#include<cstdlib>
#include<vector>
using namespace std;
struct node {
int h;
long long s;
node (long long S,int H){
s = S,h = H;
}
};
struct node1 {
int x,pos;
bool operator < (const node1 &a)const {
return x < a.x;
}
}s[45];
int n,mid,h[45],tot,cnt[45];
long long k,ans,g[45];
vector <node>L;
vector <node>R;
void dfs(int step,long long sum,int h1){
L.push_back(node(sum,h1));
if (step == mid)
return ;
for (int i = step + 1;i <= mid;i ++)
if (h[i] >= h1)
dfs(i,sum + g[i],h[i]);
}
void dfs1(int step,long long sum,int h1,int h2){
R.push_back(node(sum,h2));
if (step == n)
return ;
for (int i = step + 1;i <= n;i ++)
if (h[i] >= h1)
dfs1(i,sum + g[i],h[i],h2?h2:h[i]);
}
bool cmp(node a,node b){
return a.s > b.s;
}
bool cmp1(node a,node b){
return a.s < b.s;
}
int main(){
//freopen("san.in","r",stdin);
//freopen("san.out","w",stdout);
scanf ("%d%lld",&n,&k);
for (int i = 1;i <= n;i ++){
scanf ("%d%lld",&h[i],&g[i]);
s[i].x = h[i];
s[i].pos = i;
}
sort(s + 1 ,s + 1 + n);
for (int i = 1;i <= n;i ++){
if (s[i].x != s[i - 1].x)
h[s[i].pos] = ++ tot;
else
h[s[i].pos] = tot;
}
mid = n / 2;
dfs(0,0,0);
dfs1(mid,0,0,0);
sort(L.begin(),L.end(),cmp);
sort(R.begin(),R.end(),cmp1);
R[0].h = 41;
for (int i = 0;i < R.size();i ++)
cnt[R[i].h] ++;
int i = 0,j = 0;
while (1){
while (j < R.size() && R[j].s + L[i].s < k){
cnt[R[j].h] --;
j ++;
}
if (R[j].s + L[i].s < k)
break;
ans += R.size() - j;
for (int k1 = 1;k1 <= n;k1 ++)
if (h[k1] < L[i].h)
ans -= cnt[h[k1]];
i ++;
if (i == L.size())
break;
}
printf("%lld
",ans);
}
/*
4 6
2 1
6 3
7 2
5 6
*/
T5
题目描述
给一棵N个节点的树,编号从1到N,再给定m对点(u,v),你要将树上的每条无向边变为有向边,使得给定的点对都满足u能到达v或v能到达u。问有多少种不同的方案,答案对(1e9+7)求余。
输入
第一行两个正整数N and M(1 ≤ N, M≤ 3*1e5 ),表示树的结点个数,和点对的个数。
接下来N-1行,每行两个整数,表示树上的边。
接下来M行,每行两个不同的正整数(ai,bi),表示对应的点对,点对互不相同。
输出
一行一个数,表示不同的方案数模1e9+7
20%的数据树是一个链,即第i个点连在i+1上。
40%的数据N,M≤ 5*1e3 .
样例
样例输入1
4 1
1 2
2 3
3 4
2 4
样例输出1
4
样例输入2
7 2
1 2
1 3
4 2
2 5
6 5
5 7
1 7
2 6
样例输出2
8
样例输入3
4 3
1 2
1 3
1 4
2 3
2 4
3 4
样例输出3
0
解题思路
肯定的,树上路径有关的题直接搞LCA,同时肯定要并一块,用并查集,并且,正反两个乘法原理又与2的次方有关。然而我没管,直接搞20分的,结果炸了,输出0有近三分之一的分数。我…
正解还没码