【2017.11.04】周末胡策题
前两题水题
纵横字谜（krizaljka）
时间限制: 1 Sec 内存限制: 32 MB
题目描述
给出两个单词，找到第一个相同的字母，然后第一个单词横数输出，第二个竖着输出形成十字形。
如果两个单词有多个位置的字母相同，则先考虑在第一个单词中位置靠前的相同字母。
例如，第一个单词是 “ABBA”，第二个单词是 “CCBB”，形成的纵横字谜格式为：
.C..
.C..
ABBA
.B..
输入
第1行：2个空格分开的单词A和B，长度均不超过30个字符。
输出
令A长度为M，B长度为N，则输出共M行，每行N个字符。A单词橫着输出，B单词竖着输出。不是单词字母的位置填充句点’.’
样例输入
REPUBLIKA HRVATSKA
样例输出
H……..
REPUBLIKA
V……..
A……..
T……..
S……..
K……..
A……..
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
char a[101],b[101];
int la,lb;
int main()
{
freopen("krizaljka.in","r",stdin);
freopen("krizaljka.out","w",stdout);
scanf("%s%s",a,b);
bool flag=0;
la=strlen(a); lb=strlen(b);
int ta,tb;
for (int i=0; i<la; i++)
{
for (int j=0; j<lb; j++)
if (a[i]==b[j])
{
ta=i; tb=j; flag=1; break;
}
if (flag) break;
}
// printf("%d %d\n",ta,tb);
for (int i=0; i<lb; i++)
{
for (int j=0; j<la; j++)
{
if (j==ta) printf("%c",b[i]);
else if (i==tb) printf("%c",a[j]);
else printf(".");
}
printf("\n");
}
return 0;
}砍树（eko）
时间限制: 1 Sec 内存限制: 32 MB
题目描述
N棵树，每棵都有一个整数高度。有一个木头的总需要量M。
现在确定一个最大的统一的砍树高度H，如果某棵树的高度大于H，则高出的部分被砍下。使得所有被砍下的木材长度之和达到M（允许稍超过M）。
例如，有4棵树，高度分别是20 15 10 17， 需要的木材长度为 7，砍树高度为15时，第1棵树被砍下5，第4棵树被砍下2，得到的总长度为7。如果砍树高度为16时，第1棵树被砍下4，第4棵树被砍下1，则得到的木材数量为5。
输入
第1行：2个整数N和M，N表示树木的数量(1 ≤ N ≤ 1 000 000)，M表示需要的木材总长度(1 ≤ M ≤ 2 000 000 000)。
第2行： N个整数表示每棵树的高度，值均不超过1 000 000 000。所有木材高度之和大于M，因此必然有解。
输出
第1行：1个整数，表示砍树的最高高度。
样例输入
5 20
4 42 40 26 46
样例输出
36
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int MAXN=1000001;
int n,m,a[MAXN];
bool judge(int x)
{
int sum=0;
for (int i=1; i<=n; i++)
{
if (a[i]>x) sum+=(a[i]-x);
if (sum>=m) return true;
}
return false;
}
int main()
{
freopen("eko.in","r",stdin);
freopen("eko.out","w",stdout);
int maxn=0;
scanf("%d%d",&n,&m);
for (int i=1; i<=n; i++)
{
scanf("%d",&a[i]); maxn=max(maxn,a[i]);
}
int l=0,r=maxn;
while (l<r)
{
int mid=(l+r+1)/2;
if (judge(mid)) l=mid;
else r=mid-1;
}
printf("%d",r);
return 0;
}DNA
时间限制: 1 Sec 内存限制: 32 MB
题目描述
给出1个只有A、B组成的长度为N的字符串，现在给出两种变换方式：第一种是翻转一个字母，A变成B，或B变成A；第二种是翻转字符串某个字符的前缀（包括该字符），将前缀中所有的A变成B，或者所有的B变成A。
现在要把给出的字符串变成全A，问至少需要多少次变换操作。
输入
第1行: 一个正整数N（1<=N<=1000000）,表示字符串的长度。
第2行: N个字符，要么是A，要么是B，表示初始字符串.
输出
第1行：一个整数，表示最少需要的翻转次数
样例输入
12
AAABBBAAABBB
样例输出
4
这道题就想到了广搜。‘
dp：
分析：要么将所有的变成A，或者把所有的变成B再加一次翻转。
fa[i]:前i位都是A时的最少变换次数
fb[i]:前i位都是B时的最少变换次数
初始化memset了一下，然后90,。不知道为什么
code：
#include<cstdio>
#include<cstring>
#include<queue>
#include<algorithm>
using namespace std;
int n,fa[1000001],fb[1000001];
char ch[1000001];
int main()
{
freopen("DNA.in","r",stdin);
freopen("DNA.out","w",stdout);
scanf("%d",&n);
scanf("%s",ch);
for (int i=0; i<n; i++)
{
if (ch[i]=='A')
{
fa[i]=fa[i-1];
fb[i]=min(fa[i-1]+1,fb[i-1]+1);
}
else
{
fb[i]=fb[i-1];
fa[i]=min(fb[i-1]+1,fa[i-1]+1);
}
}
printf("%d",fa[n-1]);
return 0;
}
为什么没有想到贪心呢？
方法 从后往找，找到单个B ，ans++；找到多个B ans++； 然后翻转后继续搜。
这个当时没有想到、如何证明贪心的正确性呢？
首先，最终是要使字符串全都变成A，所以直接选B变成A肯定比都变成B之后在经过一次操作都变成A要优。
其次选一堆一起变肯定比选单个变更优。
得证。
代码实现上,怎么把单词翻转，用一个flag标记，技巧性挺强的。
code、
/*
dp:
fa[i]:前i位都是A时的最少变换次数
fb[i]:前i位都是B时的最少变换次数
*/
#include<cstdio>
#include<cstring>
#include<queue>
#include<algorithm>
using namespace std;
int n,ans;
char ch[1000001];
bool flag;
char chh(int i,bool flag)//把x及之前的反转
{
if (!flag) return ch[i];
if (ch[i]=='A') return 'B';
else return 'A';
}
int main()
{
freopen("DNA.in","r",stdin);
freopen("DNA.out","w",stdout);
scanf("%d",&n);
scanf("%s",ch+1);
int i=n;
while (i>=1)
{
if (chh(i,flag)=='B')
{
ans++; i--;
if (chh(i,flag)=='A') {i--; continue;}
while (chh(i,flag)=='B')
i--;
flag^=1;//就是取反
continue;
}
i--;
}
printf("%d",ans);
return 0;
}
/*
12
AAABBBAAABBB
*/旅行
POD
现在让我们来对一个交通运输图进行研究，这可能是一个公交车的线路网、有轨电车线路网、地下铁的线路网或是其他的一个什么。这个图中的顶点（从1到n标号）为车站，边(pi ,pj)（这里pi pj）表示在顶点pi和顶点pj间存在一条直接连接两点的路（1 pi, pj n）。在图中有从1到k编号的k条运输路线，第l号路线是用一个车站序列pl,1, pl,2, …, pl,sl来描述的，它们为使用这个线路的车辆将依次经过的车站。并且我们给出它们之间的距离rl,1, rl,2, …, rl,sl-1，其中rl,i表示从车站pl,i到车站pl,i+1所需的时间。对于一条线路来说，它上面所有的车站都是不相同的（也就是说，若i j，则pl,i pl,j）。且线路l将以频率cl运行。这里cl为集合{6, 10, 12, 15, 20, 30 ,60}中的一个数，它表示每个小时的0, cl, 2cl, …, 60分钟的时候在路线l上的将有两辆车同时从车站pl,1和pl,sl出发相对着行进。
在这样一个运输网络中，我们想从其中的一个车站x出发用尽可能少的时间到达车站y。这里我们假设最少的时间不会超过24个小时，且在中途换车的时候的时间不计。
示例：
在下图中你可以看到一个具有六个车站和两条路线的运输网络。路线一上的车站序列为1、3、4、6，路线二上的车站序列为2、4、3、5，且两条路线的频率分别为c1=15和c2=20。车辆在各车站间移动时的耗费都分别用1和2的下标标在了图上。
现在我们假设在23点30分的时候我们在车站5想要到车站6去。我们必须等上10分钟才可以搭上一辆路线2的车离开。然后我们就面临着两种选择：一种是在23点51分到车站3等上3分钟并改乘路线1的车于0点16分到达车站6；另一种是在0点8分到达车站4等上13分钟再换路线1的车于0点31分到达车站6。显然最早我们能在0点16分到达车站6。
任务：
请写一个程序：
从文本文件POD.IN中读入对该交通运输网的描述、起点和终点、还有出发的时间；
找出从起点到终点的最少时间；
把最找到达终点的时间输出到文本文件POD.OUT中。
输入格式：
在文本文件POD.IN的第一行包括六个用空格分开的整数，分别为：
n，1 n 1000，为车站的数目；
k，1 k 2000，为路线的数目；
x，1 x n，为起点的车站编号；
y，1 y n，为终点的车站编号；
gx，0 gx 23，为出发时间的小时数；
mx，0 mx 59，为出发时间的分钟数。
车站是从1到n编号的，运输路线是用1到k编号的。以下的3k行为对运输路线的描述。这些行中每3行构成一个对一条路线的描述，第k个三行的意义如下：
第一行包括两个用空格分开的整数，sl（2 sl n）为该路线上车站的数目，还有cl（{6, 10, 12, 15, 20, 30, 60}中的一个元素），为该路线运行的频率；
第二行包括sl个用空格分开的不同的整数，为pl,1, pl,2, …,pl,sl（1 pl,i n），即该路线上的车站；
第三行包括sl-1个整数rl,1, rl,2, …,rl,sl-1为在路线上相邻两个车站间移动所需的时间（1 rl,i 240）。
在所有的运输路线上的总车站数不超过4000（也就是说s1 + s2 + … + sk 4000）。
输出格式：
你的程序应该在文本文件POD.OUT中输出两个整数gy（0 gy 23）和my（0 my 59），表示到达y点时的小时数和分钟数。
样例：
输入（POD.IN）：
6 2 5 6 23 30
4 15
1 3 4 6
9 12 10
4 20
5 3 4 2
11 17 11
输出（POD.OUT）：
0 16
这道题还是不错的。考察了基础算法
有限制的最短路问题
问题转述：
给定某一动态图G，图中的边权为时间，且边将以一定的周期切换它们的存在状态。试求从图中某点到另一点得最短时间。
刚开始拿到这道题，想到的是什么dp。实际上跑一个最短路。
好像每一条线路都有很多信息，怎么处理呢？ 把这些信息都放到每一条边里面。c记录这一条边上的频率，ti记录从起点到达这一条边的距离。（有一些小技巧）有当前的时间，发车的频率，以及车到这个点的时间，就可计算出最快坐上车的时间（最短等待时间）。然后与普通的SPFA不同的是，我把wait的时间加到了每一条边的权值上。还有要乘这一路车的时候，应该选一个等待时间最短的。
除去一些细节方面的东西，就是裸的最短路了。
所以说基础算法还是要学好的，可以解决很多问题
edge应该是开两倍的（WA1 TLE1）
数组不要开小！
#include<cstdio>
#include<cstring>
#include<queue>
#include<algorithm>
using namespace std;
const int MAX_INT=0x7fffffff;
int n,k,x,y,gx,mx,num,c,p[1001],t[1001];
struct Edge{
int next,to,c,ti,dis;
}edge[8001];
int head[1001],num_edge;
void add_edge(int from,int to,int dis,int c,int time)
{
edge[++num_edge].next=head[from];
edge[num_edge].to=to;
edge[num_edge].dis=dis;
edge[num_edge].c=c;
edge[num_edge].ti=time;
head[from]=num_edge;
}
void init()
{
scanf("%d%d%d%d%d%d",&n,&k,&x,&y,&gx,&mx);
for (int i=1; i<=k; i++)
{
scanf("%d%d",&num,&c);
int sum=0;
for (int j=1; j<=num; j++) scanf("%d",&p[j]);
for (int j=1; j<=num-1; j++)
{
scanf("%d",&t[j]); sum+=t[j];
}
int s1=0,s2=0;
for (int j=1; j<=num-1; j++)
{
s2+=t[j];
add_edge(p[j],p[j+1],t[j],c,s1);
add_edge(p[j+1],p[j],t[j],c,sum-s2);
s1+=t[j];
}
}
}
int team[5001],dis[1001];
bool b[1001],vis[1001];
void SPFA()
{
memset(dis,0x7f/3,sizeof(dis));
team[1]=x; b[x]=true; vis[x]=true; dis[x]=0;
int front=0,tail=1;
while (front<=tail)
{
int now=team[++front];
b[now]=false;
for (int i=head[now]; i!=0; i=edge[i].next)
{
if (!vis[edge[i].to])
{
int k=1;
int people=mx+dis[now]; people%=60;//人到达这个点的时间
int wait=MAX_INT;
while (k*edge[i].c<=60)
{
k++;
int bus=k*edge[i].c+edge[i].ti; bus%=60;//这一路车到达的时间
wait=min(wait,(bus-people+60)%60);
}
if (dis[edge[i].to]>dis[now]+wait+edge[i].dis)
{
dis[edge[i].to]=dis[now]+wait+edge[i].dis;
if (!b[edge[i].to])
{
b[edge[i].to]=true;
team[++tail]=edge[i].to;
}
}
}
}
}
}
int main()
{
freopen("POD.in","r",stdin);
freopen("POD.out","w",stdout);
init();
SPFA();
// printf("%d",dis[y]);
mx+=dis[y];
gx+=mx/60; gx%=24;
mx%=60;
printf("%d %d",gx,mx);
return 0;
}
/*
6 2 5 6 23 30
4 15
1 3 4 6
9 12 10
4 20
5 3 4 2
11 17 11
0 16
*/