2019年安徽省程序设计大赛题解
本题解所有代码均通过完整数据检测。
A:机器人足球
时间：1 s
题目描述：
足球场地长为100,宽为20,对方的球门坐标为(100,10),你要控制一个个机器人踢球，初始位置为(x,y).机器人可以朝任何方向移动，但不能超出场地边界，当机器人与球门距离不超过10时，可以射门。 问机器人从初始位置出发到射门，最少要移动多少距离? (四舍五人到小数点后3位)
输入
每组输人为2个整数，分别为x ,y
0<= x<=100
0<= y<=20
输出
输出最小移动的距离
样例输入
10 10
样例输出
80.000
题解
模拟
#include<bits/stdc++.h>
using namespace std;
int x,y;
float d;
int main(){
scanf("%d%d",&x,&y);
d=sqrt((100-x)*(100-x)+(10-y)*(10-y));
if(d<=10)printf("0.000");
else printf("%.3lf",d-10);
return 0;
}
B:纸牌识别
时间：3 s
题目描述：
Alice沉迷于机器人研究，他打算做- - 个机器人来检查-副扑克是否完整。现在，他想请你帮他写-一个程序，来识别纸牌，每张纸牌都有-个花色(四种花色，分别用大写字母P，K, H, T表示)和一一个数字点数(1-13) .纸牌可以用ABC的形式来表示，A代表花色，BC代表数字，如果数字小于10，会有一位补0.
比如花色是P,数字是9的纸牌会表示成P09.一副完整的纸牌有52张牌，四种不同的花色各有1张数字1-13的牌.你的程序要读人一个字符串，表示缺少的纸牌有哪些。如果包含相同的纸牌(花色数字都相同)输出GRESKA,否则输出每种花色剩余的纸牌数量。
输入
输人只有一行，一个字符串S, S的长度长度小于等于1000
输出
如果输人中包含相同的纸牌，输出GRESKA,否则分别输出四个整数，代表P,K, H, T四种花色纸牌的剩余数量
样例输入
P01K02H03H04
样例输出
12 12 11 13
题解
模拟
#include<bits/stdc++.h>
using namespace std;
const int maxn=1005;
char s[maxn];
int a[5][15];
int main(){
scanf("%s",s+1);
int len=strlen(s+1);
for(int i=2;i<=len;i=i+3){
int num=0;
num=(s[i]-'0')*10+(s[i+1]-'0');
if(s[i-1]=='P')a[1][num]++;
else if(s[i-1]=='K')a[2][num]++;
else if(s[i-1]=='H')a[3][num]++;
else a[4][num]++;
}
for(int i=1;i<=4;i++){
int num=0;
for(int j=1;j<=13;j++){
if(a[i][j]==1)num++;
else if(a[i][j]>1){
printf("GRESKA");
return 0;
}
}
a[i][0]=13-num;
}
for(int i=1;i<=4;i++){
printf("%d ",a[i][0]);
}
return 0;
}
C:卡牌对决
时间：3 s
题目描述：
有2N张牌，它们的点数分别为1到2N。Alice拿了其中的N张，Bob拿了剩下的N张. Alice和Bob会进行N轮游戏，在每轮游戏中，Alice 和Bob 各出一张牌。出了的牌不能收回。在前N/2轮中，每轮谁的牌点数大谁就赢;在后N/2轮中，每轮谁的牌点数小谁就赢。已知Bob 每一轮会出什么牌，试求Alice 最多能赢多少轮。
输入
第一行是一个整数N,
接下来N行，每行一个整数，表示Bob这轮会出什么。
2<=N <= 50000,保证N是偶数
输出
输出Alice最多能赢几轮
样例输入
4
1
8
4
3
样例输出
2
题解
贪心
#include<bits/stdc++.h>
using namespace std;
const int maxn=100005;
int n,a[maxn],A[maxn],B1[maxn/2],B2[maxn/2];
int numa=1,numb=1,ans;
int main(){
scanf("%d",&n);
for(int i=1;i<=n/2;i++){
int tmp;
scanf("%d",&tmp);
a[tmp]=1;
B1[numb++]=tmp;
}
numb=1;
for(int i=n/2+1;i<=n;i++){
int tmp;
scanf("%d",&tmp);
a[tmp]=1;
B2[numb++]=tmp;
}
for(int i=1;i<=2*n;i++){
if(!a[i])A[numa++]=i;
}
sort(A+1,A+n+1);
sort(B1+1,B1+n/2+1);
sort(B2+1,B2+n/2+1);
int t=n/2+1;
int k=1;
while(k!=(n/2+1)&&t!=(n+1)){
if(A[t]>B1[k]){
ans++;
k++;
t++;
}
else{
t++;
}
}
k=n/2;
t=n/2;
while(k!=0&&t!=0){
if(A[t]<B2[k]){
ans++;
k--;
t--;
}
else{
t--;
}
}
printf("%d",ans);
return 0;
}
D:自驾游
时间：2 s
题目描述：
P省有N个城市，编号分别为1…N,烦烦家住 1号城市，N号城市是省会，P省的交通非常发达，有M条有向的高速公路连接这N个城市，第i条高速公路(1<=i<=M)从城市ui连向城市vi。
这天，烦烦想自己开车从家前往省会城市游玩.烦烦是个做事很细致的人，为了有备无患，她决定同时开着heroMap和amap这两个不同的导航软件来帮助白已完成这次旅程，这两个导航软件内部采用了不同的算法，对于第i条高速公路(1<=i<=M)，heromap 认为通过时间为Pi分钟，amap 则认为通过时间为Qi分钟。这两个导航软件会根据自己的数据来计算从当前位置到目标位置所需的短时间是多少，对于第i个城市(1<=i<=N),记heromap认为从i到N把时间为heor(i),记amap认为到i到N的最短时间为a(i)。烦烦开车途经某条高速公路(1<=i<=M)时，如果heromap认为从ui到N不应该走这条路，即hero(vi)+Pi>hero(ui),则发出一次警告，同样的，如果amap认为从ui到N不应该走这条路，即a(vi)+Qi>a(ui),也会发出一次警告。
现在烦烦希望自己选择选择一条路径，使得收到的警告总数最少，请你编程解决这一问题。
输入
第一行是两个整数N和M。N表示城市数目，M表示连接N个城市的公路数。
接下来M行，第i行有四个整数ui,vi,Pi,Qi,分别表示第i条边的出发点和到达点编号，两个导航软件认为走这条边所用的时间。
2<=N<=10,000
1<=M<=50,000
1<ui,vi<=N
输出
输出从1走到N最少收到多少次警告
样例输入
5 7
3 4 7 1
1 3 2 20
1 4 17 18
4 5 25 3
1 2 10 1
3 5 4 14
2 4 6 5
样例输出
1
题解
最短路
#include<bits/stdc++.h>
using namespace std;
const int maxn=10005;
const int maxm=50005;
const int inf=0x3fffffff;
int n,m;
struct edge {
int amap;
int hero;
int next;
int to;
};
struct new_edge{
int to;
int dis;
};
edge e[maxm];
vector<new_edge> v[maxn];
int cnt,head[maxn],d1[maxn],d2[maxn],d3[maxn];
bool vis[maxn];
inline void add_edge(int u,int v,int w,int x){
cnt++;
e[cnt].to=v;
e[cnt].hero=w;
e[cnt].amap=x;
e[cnt].next=head[u];
head[u]=cnt;
}
struct node{
int dis;
int pos;
bool operator <(const node &x)const{
return x.dis<dis;
}
};
priority_queue<node>q;
void dij1(int s){
fill(d1,d1+maxn,inf);
d1[s]=0;
q.push((node){0,s});
while(!q.empty()){
node tmp=q.top();
q.pop();
int x=tmp.pos;
vis[x]=true;
for(int i=head[x];i;i=e[i].next){
int y=e[i].to;
if(d1[y]>d1[x]+e[i].hero){
d1[y]=d1[x]+e[i].hero;
if(!vis[y]){
q.push((node){d1[y],y});
}
}
}
}
}
void dij2(int s){
fill(vis,vis+maxn,false);
fill(d2,d2+maxn,inf);
d2[s]=0;
q.push((node){0,s});
while(!q.empty()){
node tmp=q.top();
q.pop();
int x=tmp.pos;
vis[x]=true;
for(int i=head[x];i;i=e[i].next){
int y=e[i].to;
if(d2[y]>d2[x]+e[i].amap){
d2[y]=d2[x]+e[i].amap;
if(!vis[y]){
q.push((node){d2[y],y});
}
}
}
}
}
void dij3(int s){
fill(vis,vis+maxn,false);
fill(d3,d3+maxn,inf);
d3[s]=0;
q.push((node){0,s});
while(!q.empty()){
node tmp=q.top();
q.pop();
int x=tmp.pos;
vis[x]=true;
for(int i=0;i<v[x].size();i++){
new_edge tmp2=v[x][i];
int y=tmp2.to;
if(d3[y]>d3[x]+tmp2.dis){
d3[y]=d3[x]+tmp2.dis;
if(!vis[y]){
q.push((node){d3[y],y});
}
}
}
}
}
int main(){
scanf("%d%d",&n,&m);
for(int i=1;i<=m;i++){
int u,v,w,x;
scanf("%d%d%d%d",&u,&v,&w,&x);
add_edge(v,u,w,x);
}
dij1(n);
dij2(n);
for(int i=1;i<=n;i++){
for(int j=head[i];j;j=e[j].next){
new_edge tmp;
tmp.dis=0;
if(d1[i]+e[j].hero>d1[e[j].to])tmp.dis++;
if(d2[i]+e[j].amap>d2[e[j].to])tmp.dis++;
tmp.to=i;
v[e[j].to].push_back(tmp);
}
}
dij3(1);
printf("%d",d3[n]);
return 0;
}
E：现代艺术
时间：2 s
题目描述：
给出平面上 N 个点的坐标点集， 求这 N 个点有多少条整体对称轴。整体对称是指一条直线，对于每个点，都能找到点集的一个点与他关于这条直线对称。
输入
第一行是一个整数N，表示点的个数
接下来 N 行，每行两个整数 X, Y，表示点的坐标
2 <= N <= 1000
-10000 <= X, Y <= 10000
输出
输出点集的整体对称轴有多少条
样例输入
4
0 0
0 1
1 0
1 1
样例输出
4
题解：
计算几何
#include<bits/stdc++.h>
using namespace std;
const int maxn = 1005;
struct Point {
double x, y;
} p[maxn];
set<float> q; //保存整体对称轴的斜率,set的size就是整体对称轴的条数
double cross(Point a, Point b, Point c) { //叉积
return ((b.x - a.x) * (c.y - a.y) - (b.y - a.y) * (c.x - a.x));
}
double dis(Point a, Point b) { //两点距离
return sqrt((a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y));
}
bool cmp(Point a, Point b) {
if (cross(p[0], a, b) == 0)
return dis(a, p[0]) < dis(b, p[0]);
else
return cross(p[0], a, b) > 0;
}
double k(Point a, Point b) { //斜率
if (a.x == b.x)
return double(1e9);
else if (a.y == b.y)
return 0;
else
return (b.y - a.y) / (b.x - a.x);
}
int main() {
int n;
cin >> n;
Point ave; //平均值 点
ave.x = 0;
ave.y = 0;
for (int i = 0; i < n; ++i) {
cin >> p[i].x >> p[i].y;
ave.x += p[i].x;
ave.y += p[i].y;
}
ave.x /= n;
ave.y /= n;
//开始求凸包
for (int i = 1; i < n; ++i) {
if ((p[i].y < p[0].y))
swap(p[0], p[i]);
else if (p[i].y == p[0].y && p[i].x < p[0].x)
swap(p[i], p[0]);
}
sort(p + 1, p + n, cmp);
int tot = 1;
for (int i = 2; i < n; ++i) { //手写栈
while (tot > 0 && cross(p[tot - 1], p[tot], p[i]) <= 0) tot--;
tot++;
p[tot] = p[i];
}
Point temp; //凸包线段上的中点
bool flag = 0;
int ans = 0;
q.clear();
for (int i = 0; i <= tot; ++i) {
for (int j = i + 1; j <= tot; ++j) {
temp.x = (p[i].x + p[j].x) / 2;
temp.y = (p[i].y + p[j].y) / 2;
flag = 0;
if (float(temp.x - ave.x) * (p[i].x - p[j].x) +
float(temp.y - ave.y) * (p[i].y - p[j].y) ==
0) {//经过平均值点的凸包上的中垂线即为整体对称轴
flag = 1;
}
if (flag) {
if (temp.x == ave.x && temp.y == ave.y)
q.insert(k(p[i], p[j]));
else {
q.insert(k(temp, ave));
}
}
}
}
ans=q.size();
if (tot == 1) ans++;
cout <<ans << endl;
return 0;
}
F:邻家割草
时间限制 ：3 s
题目描述：
邻居 Alice 家 有一块大草坪， 每个一段时间他都要用割草机修剪草坪； 可以把草坪看成是一个 N * M 的矩阵， 割草时需要 N 台割草机水平方向穿过草地， M 台割草机垂直方向穿过草地。草地并不是完全平整的， 有高有低； 如图所示，高的地方用深色表示， 矮的地方用浅色表示。
割草机工作时需要消耗燃油， 在走过不同的高度的草地时， 会消耗 A 元燃油费； （比如从低的地方走到高的地方， 从高的地方走到低的地方， 在相同高度的地块上运行割草机的燃油消耗可以忽略）。Alice 为了节省燃油费， 准备改造一些地形； 可以给一些地块加入来升高地形，或者把高的地方铲平来降低地形高度，对一个地块进行改造需要花费 B 元。你能帮邻居 Alice 设计一个方案。 让他花费最小吗？
输入
输人的第一行是四个整数N M A B,分别表示矩阵有N行，M列;走过不同高度的地块需要多花费A元;调整地块高度需要花费B元.
接下来N行，每行M个字符，描述来草坪地形。’#代表高的地块， 字符:代表低的地块。
1 <=N,M<= 50
输出
输出 Alice 改造地块 + 割草的最小花费
样例输入
5 4 1000 2000
. . . #
# . . #
. . . #
# # . .
# # # .
样例输出
11000
提示
Alice 的草地大小是 5 x 4 .在不同高度的地块上行走每个割草机要多花费1000元，调整一个地块的地形需要花费2000元;Alice 最少需要 11000 元。2000 元用于修改第行第一个地块，把这个地块的高度降低。9000元用于割草，水平方向运行的5台割草机花费5000元，垂直方向运行的4台割草机花费4000元。
题解：
最小割
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
const int N = 1e6+10, INF = 0x3f3f3f3f;
int n, m, a, b, S, T;
char s[55][55];
struct edge {
int v,next;
ll w;
edge () {}
edge (int v,int next,ll w) :v(v),w(w),next(next) {}
} e[N];
int head[N], dep[N], vis[N], cur[N], cnt=1;
queue<int> Q;
pii get(int t) {
int x = (t-1)/m+1, y = (t-1)%m+1;
return pii(x,y);
}
void add(int u, int v, ll w) {
e[++cnt] = edge(v,head[u],w);
head[u] = cnt;
e[++cnt] = edge(u,head[v],0);
head[v] = cnt;
}
int bfs() {
for(int i=1;i<=T;i++) dep[i]=INF,vis[i]=0,cur[i]=head[i];
dep[S]=0,Q.push(S);
while (Q.size()) {
int u = Q.front(); Q.pop();
for (int i=head[u]; i; i=e[i].next) {
if (dep[e[i].v]>dep[u]+1&&e[i].w) {
dep[e[i].v]=dep[u]+1;
Q.push(e[i].v);
}
}
}
return dep[T]!=INF;
}
ll dfs(int x, ll w) {
if (x==T) return w;
ll used = 0;
for (int i=cur[x]; i; i=e[i].next) {
cur[x] = i;
if (dep[e[i].v]==dep[x]+1&&e[i].w) {
int flow = dfs(e[i].v,min(w-used,e[i].w));
if (flow) {
used += flow;
e[i].w -= flow;
e[i^1].w += flow;
if (used==w) break;
}
}
}
return used;
}
ll dinic() {
ll ans = 0;
while (bfs()) ans+=dfs(S,1e18);
return ans;
}
int id(int x, int y) {
return (x-1)*m+y;
}
int main() {
scanf("%d%d%d%d", &n, &m, &a, &b);
for(int i=1;i<=n;i++) scanf("%s",s[i]+1);
S = n*m+1, T = S+1;
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++) {
if (s[i][j]=='.') add(S,id(i,j),b);
else add(id(i,j),T,b);
if (i!=n) {
if (s[i][j]=='.'&&s[i+1][j]=='#') add(id(i,j),id(i+1,j),a);
else add(id(i+1,j),id(i,j),a);
if (s[i][j]==s[i+1][j]) add(id(i,j),id(i+1,j),a);
}
if (j!=m) {
if (s[i][j]=='.'&&s[i][j+1]=='#') add(id(i,j),id(i,j+1),a);
else add(id(i,j+1),id(i,j),a);
if (s[i][j]==s[i][j+1]) add(id(i,j),id(i,j+1),a);
}
}
printf("%lld\n", dinic());
}
G:括号序列
时间：2 s
题目描述：
括号序列是指由 ‘(’ 和 ‘)’ 组成的序列，假如一个括号序列中，包含相同数量的左括号和右括号，并且对于每一个右括号，在他的左侧都有左括号和他匹配，则这个 括号序列就是一个合法括号序列，如（（ ））（ ）就是一个合法括号序列，但（（ ））（（ ）不是合法括号序列.
给出两个长度相同的合法括号序列 A 和 B , 那么 A < B 当且仅当:
- A和B至少有一位不相同
- 在A和B从左往右数第一个不相同的位置i,A[i] = ( ,B[i]= ) ;
比如A = （（ ））（）, B = （ ）（ ） （ ）， 则 A < B 。因为从左边数第一个不相同的是第二个字符，A[2] = ( , B[2] = )。对于长度 N，由于定义了小于关系，则可以通过这个关系推出所有长度为N的合法括号序列的大小关系，对于长度为6的合法括号序列，从小到大排列顺序如下:
-
（（（ ）））
-
（（）（））
-
（（ ））（ ）
-
（ ）（（ ））
-
（ ）（ ）（ ）
给出 N 和 M， 求长度为 N 的合法括号序列中， 第 M 小的合法括号序列是？
输入
输入的第一行是 N 和 M
2 <= N <= 2000
1 <= M <= 10^18
输出
输出一个字符串，表示长度为 N 的平衡括号序列从小到大排列， 序号为 M 的字符串
样例输入
6 2
样例输出
( ( ) ( ) )
题解
动态规划
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=2010;
const ll inf=1e18+1;
int n,k;
ll f[maxn][maxn];
char ans[maxn];
int main(){
scanf("%d%d",&n,&k);
dp[0][0]=1;
for(int i=1;i<=n;i++){
for(int j=0;j<=n;j++){
if(f[i-1][j]){
f[i][j+1]+=f[i-1][j];
if(j)f[i][j-1]+=f[i-1][j];
f[i][j+1]=min(f[i][j+1],inf);
if(j)f[i][j-1]=min(f[i][j-1],inf);
}
}
}
int now=0;
for(int i=1;i<=n;i++){
if(f[n-i][now+1]>=k)ans[i]='(',++now;
else ans[i]=')',k-=f[n-i][now+1],--now;
}
puts(ans+1);
return 0;
}
H:不要回文
时间：2 s
题目描述：
给出一个字符串 S，你需要尽可能少的修改 S 中的字符， 使得 S 不包含长度大于等于 2 的回文子串。
输入
输入的第一行是一个字符串 S， S只包含小写字母
S 的长度大于 5 小于 300
输出
输出使得 S 中不包含长度大于等于 2 的回文， 最少需要修改几个字符 （可以修改成任意字符）
样例输入
abbaa
样例输出
2
题解
思维题，贪心
#include<bits/stdc++.h>
using namespace std;
int a[305],ans=0;
int t=30;
string s;
int main(){
cin>>s;
int len=s.length();
for(int i=0;i<len;i++){
a[i+1]=s[i]-'a'+1;
}
for(int i=1;i<=len;i++){
if(a[i]==a[i+2]){
if(a[i]==a[i-1]){
a[i]=t++;
ans++;
}
else a[i+2]=t++,ans++;
}
}
for(int i=1;i<=len;i++){
if(a[i]==a[i+1]){
a[i+1]=t++;
ans++;
}
}
cout<<ans;
return 0;
}
I:你的名字
时间：2 s
描述：
Alice 想要计算他那 N 只猫的名字的价值每只猫的名字由不超过 1000 个大小写字母构成，没有一个名字是空字体串。 Alice有一张*价值字符串表”， 上面有 M个代表价值的字符串。每个字符串由不超过30个大小写字母构成，同样不存在空字符串。一个猫的名字蕴含多少个价值字符串，这个名字就有多少价值，所谓 “蕴含”，是指某个能量字符串的所有字符都在名字串中按顺序出现 (不一定一个紧接着一个) .
所有的大写字母和小写字母都是等价的。比如，在贝黄的名字"Bessie"里， 蕴含有 “Be” “si” “EE” 以及 “Es” 等等字符串，但不蕴含"Ls°或"eB"请帮Alice计算他的猫的名字的价值.
输入
输人的第-行是两个整数 N M
接下来N行，每行一个字符串表示猫的名字。
接下来M行，每行一个价值字符串
1 <=N<= 1000
1 <= M<=100
输出
输出每只猫蕴含多少个价值字符串。
样例输入
5 3
Bessie
Jonathan
Montgomery
Alicia
Angola
Se
nGo
oNt
样例输出
1
1
2
0
1
题解
暴力
#include<bits/stdc++.h>
using namespace std;
int n,m;
char cat[1005][1005];
char str[105][35];
int main(){
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++){
scanf("%s",cat[i]+1);
int len=strlen(cat[i]+1);
for(int j=1;j<=len;j++){
cat[i][j]=tolower(cat[i][j]);
}
}
for(int i=1;i<=m;i++){
scanf("%s",str[i]+1);
int len=strlen(str[i]+1);
for(int j=1;j<=len;j++){
str[i][j]=tolower(str[i][j]);
}
}
for(int i=1;i<=n;i++){
int ans=0;
int catlen=strlen(cat[i]+1);
for(int j=1;j<=m;j++){
int slen=strlen(str[j]+1);
int p=1,q=1;
while(p<=catlen&&q<=slen){
if(cat[i][p]==str[j][q]){
p++,q++;
}
else p++;
}
if(q==slen+1)ans++;
}
printf("%d\n",ans);
}
return 0;
}
序列自动机
#include<bits/stdc++.h>
using namespace std;
int n,m;
char cat[1005][1005],str[105][35];
int nxt[1001][1001][26];
int main(){
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++){
scanf("%s",cat[i]+1);
int len=strlen(cat[i]+1);
for(int j=1;j<=len;j++){
cat[i][j]=tolower(cat[i][j]);
}
for(int j=len;j>=1;j--){
if(j==len){
for(int k=0;k<=25;k++){
nxt[i][j][k]=len+1;
}
}
for(int k=0;k<=25;k++){
nxt[i][j-1][k]=nxt[i][j][k];
}
nxt[i][j-1][cat[i][j]-'a']=j;
}
}
for(int i=1;i<=m;i++){
scanf("%s",str[i]+1);
int len=strlen(str[i]+1);
for(int j=1;j<=len;j++){
str[i][j]=tolower(str[i][j]);
}
}
for(int i=1;i<=n;i++){
int ans=0,catlen=strlen(cat[i]+1);
for(int j=1;j<=m;j++){
int p=0,flag=1;
int slen=strlen(str[j]+1);
for(int k=1;k<=slen;k++){
p=nxt[i][p][str[j][k]-'a'];
if(p>catlen){
flag=0;
break;
}
}
if(flag)ans++;
}
printf("%d\n",ans);
}
return 0;
}
J：密信
时间:3 s
题目描述：
Alice 想给 Bob 发短信，短信的内容可以看成是一个只有小写字母的字符串 p;为了加密短信，Alice 需要只有小写字母长度为 n 的字符串 h ,并且 p 是 h 的子串: Alice 想知道，这样的字符串有多少种。
给出 n 和 M 还有字符串 p ,假设一共有 K 种不同的 h ,输出K mod M
输入
输人包含多组数据，第一行是组数 T , T ≤= 50
对于每组测试数据，第一行是 n M
接下来一行是字符串 p
n,M <= 10 ^ 12
P 是一个长度不大于 50 且只有小写字母的字符串
输出
输出 K mod M
样例输入
2
2 100
ab
3 100
ab
样例输出
1
52
题解
动态规划+矩阵优化
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const int N = 55;
ll n, M;
int len, f[N];
char s[N];
void getFail() {
int j = 0;
for(int i=1;i<=len-1;i++){
while (j&&s[j]!=s[i]) j=f[j];
if (s[j]==s[i]) ++j;
f[i+1] = j;
}
}
ull qmul(const ull a, const ull b, const ull md) {
ll c=(ll)a*b-(ll)((ull)((long double)a*b/md)*md);
return c<0?md+c:((ull)c>md?c-md:c);
}
struct Mat {
ll v[55][55];
Mat() {memset(v, 0, sizeof v);}
Mat operator * (const Mat& b) const {
Mat c;
for(int k=0;k<=len;k++)
for(int i=0;i<=len;i++)
for(int j=0;j<=len;j++){
c.v[i][j] = (qmul(v[i][k],b.v[k][j],M)+c.v[i][j])%M;
}
return c;
}
Mat operator ^ (ll nn) {
Mat b, a=*this;
for(int i=0;i<=len;i++)
b.v[i][i]=1;
while(nn) {
if(nn&1LL) b=b*a;
nn>>=1LL,a=a*a;
}
return b;
}
};
int main() {
int t;
scanf("%d", &t);
while (t--) {
scanf("%lld%lld%s", &n, &M, s);
len = strlen(s);
getFail();
Mat g;
for(int i=0;i<=len;i++)
for(int k='a';k<='z';k++) {
int nxt = i;
while (nxt&&s[nxt]!=k) nxt = f[nxt];
if (s[nxt]==k) ++nxt;
if (i==len) nxt = len;
++g.v[nxt][i];
}
g = g^n;
printf("%lld\n", g.v[len][0]);
}
}
K：福报
时间： 2 s
题目描述：
员工绩效评估对于任何公司都是很重要的，在绩效考核中，员工会就最近完成的工作编写工作反馈。反馈会被递给他们的上级，然后上级根据收到的反馈来决定绩效.
Alice 负责-家知名公司工程部广]的绩效考核系统。该部门遵循树形结构。每位员工都有一个直接上级，最上级是部门总监.
让上级评估其直接下属的表现并不是很有效.经过深人研究，Alice 想出了一个新的绩效考核系统，主要思路是在现有的公司结构中补充每个员工的技术等级，新的绩效评估流程如下，员工要准备他们的工作反馈，然后向所有比他技术等级高的上级(直接上级和间接上级)递交工作反馈;上级需 要花时间审核所有递交给他的工作反馈。
Alice 对这个新系统感到非常满意，但她不确定这在实践中是否可行，她想知道每个员工审核下属工作反馈所需的时间，你能帮她吗?
输入
输人的第一行是整数 E , 员工的总数。接下来有 E 行，第 i 行有三个整数mi,ri ,ti表示第 i 号员工对应的上级编号，他的技术等级，审核他的工作反馈所需要的时间，部门总监没有上级，所以他的上级编号是 -1
1 < E, mi, ri,ti < 10^6
输出
按编号顺序输出每位员工审核下属工作1反馈所需时间
样例输入
5
4 4 80
1 1 40
-1 10 60
3 5 50
4 8 70
样例输出
40
0
240
120
0
提示
1号审核2号，花费时间40
2号是叶子节点，没有下属
3号审核4号，1号，5号，2号，花费时间80+40+50+70=240
4号审核1号，2号，花费时间80+40=120
5号没有下属
题解:
dfs序上区间查值
#include<bits/stdc++.h>
#define lowbit(x) ((-x)&(x))
using namespace std;
typedef long long ll;
const int maxn=1e6+5;
struct node{
int id,r,t;
};
vector<int>g[maxn];
node a[maxn];
int in[maxn],out[maxn],n,root,cnt;
ll c[maxn],ans[maxn];
bool cmp(node a,node b){
return a.r<b.r;
}
void dfs(int x){
in[x]=++cnt;
for(int i=0;i<g[x].size();i++){
int y=g[x][i];
dfs(y);
}
out[x]=cnt;
}
void add(int x,int t){
for(int i=x;i<=n;i+=lowbit(i)){
c[i]+=t;
}
}
ll query(int x){
ll res=0;
for(int i=x;i>=1;i-=lowbit(i)){
res+=c[i];
}
return res;
}
int main(){
scanf("%d",&n);
for(int i=1;i<=n;i++){
int u;
scanf("%d%d%d",&u,&a[i].r,&a[i].t);
a[i].id=i;
if(u>0) g[u].push_back(i);
else root=i;
}
dfs(root);
sort(a+1,a+1+n,cmp);
for(int i=1;i<=n;i++){
int j=i;
while(a[j+1].r==a[i].r)j++;
for(int k=i;k<=j;k++){
ans[a[k].id]=query(out[a[k].id])-query(in[a[k].id]);
}
for(int k=i;k<=j;k++){
add(in[a[k].id],a[k].t);
}
i=j;
}
for(int i=1;i<=n;i++){
printf("%lld\n",ans[i]);
}
return 0;
}
L：曲奇工厂
时间 :2 s
题目描述：
曲奇工厂是一个经典好玩的益智游戏，游戏中你的目标是生产至少 C 块曲奇:游戏的规则十分简单; 游戏开始时你有 0 块曲奇，每分钟可以手工作出 S 块曲奇。你也可以从 N 个工厂中选择些买下来; 工厂依次编号为 1-N ,买下第 i 个工厂需要花费 Ai 个曲奇饼。但是工厂会为你带来更多收益，买下第 i 个工厂后，每分钟曲奇产出会增加 Bi 块。
对于每个工厂，你只能买一次: 你只能在整数分钟时购买工厂，并且可以一次买多个工厂, 请问达成日标所用最短时间是多少?
输入
输人的第一行是三个整数 N, C 和 S
接下来 N 行，每行两个整数 Ai 和 Bi
1 <=N<= 5
1<= C, S, Ai, Bi <=.10^5
输出
输出得到至少C块曲奇,最少要多长时间。
样例输入
2 18 1
6 2
5 1
样例输出
12
题解
搜索
#include<bits/stdc++.h>
using namespace std;
const int N = 10;
int n, c, s, cnt;
int f[N];
struct {
int x,y;
} a[N], b[N], d[N];
int ans;
int calc(int n) {
int sum = 0, v = s, ans = 0;
for(int i=1;i<=n;i++) {
if (sum<d[i].x) {
int t = (d[i].x-sum+v-1)/v;
sum += t*v;
ans += t;
}
sum -= d[i].x;
v += d[i].y;
}
if (sum<c) ans += (c-sum+v-1)/v;
return ans;
}
void dfs(int now) {
if (now>n) {
for(int i=1;i<=cnt;i++) f[i] = i;
do {
for(int i=1;i<=cnt;i++) d[i]=b[f[i]];
ans = min(ans, calc(cnt));
} while (next_permutation(f+1,f+1+cnt));
}
else {
dfs(now+1);
b[++cnt] = a[now];
dfs(now+1);
--cnt;
}
}
int main() {
scanf("%d%d%d", &n, &c, &s);
for(int i=1;i<=n;i++)
scanf("%d%d",&a[i].x,&a[i].y);
ans = (c+s-1)/s;
dfs(1);
printf("%d\n", ans);
}
