- 霸气的车牌(car)
【题目描述】
6Bit 开车总能碰到一些霸气的车牌，这不，等红灯的功夫就又遇到了两个。 当然还有 kiki 的 APL777 也是很霸气的。
6Bit 认为车牌号只要里面有回文部分，就是比较霸气的，回文就是指车牌号
轴对称，回文的长度越长，其霸气度就越大。
A4444A 的霸气度就是 6，霸气回文段就是 A4444A。 A33K33 的霸气度就是 5，霸气回文段就是 33K33。 APL777 的霸气度就是 3，霸气回文段就是 777。
然而 6Bit 的车牌 ACZ607 就不霸气……
现在给你一个车牌号，让你帮忙算出此车牌的霸气值是多少，并且输出对应的霸气回文段。如果车牌 不霸气，则直接输出-1。
【输入】 第一行一个字符串，表示一个车牌号。
【输出】 输出第一行一个整数，表示车牌号的霸气值。
输出第二行一个字符串，表示车牌号对应的霸气回文段（数据保证答案唯一）。
【输入输出样例】
car.in car.out
A33K33 5
33K33
【数据范围】
对于一个正常的车牌号，长度为 6。
没错 ，本题就是奇坑无比的字符串处理
llq表示这题就是考我们会不会编程
严重表示 90的我 感觉不会编程
这题好坑有没有………
好麻烦
比较奇怪的是有人打表90
我和我的小伙伴们都惊呆了………..
太有毅力了；（什么习惯…打分号）
本人比较推荐的方式是wyf的做法
后来用他的方法也写了一个
就a了
利用函数
从两边向中间找
因为是回文 所以自然对称
用while做就十分简单了；（又是分号）
bool函数的判断…
值得说明的是
如果长度是1…
一定要输出-1
坑有没有！！！！！
我的代码如下
觉的长的同志忍一忍……….
#include <stdio.h>
#include <string.h>
#include <algorithm>
#include <iostream>
using namespace std;
char str[10];
bool check(int l,int r)
{
bool aa;
aa=1;
while(1)
{
if(l>r)
{
return 1;
}
if(str[l]!=str[r])
{
return 0;
}
l++;
r--;
}
}
int main()
{
freopen("car.in", "r", stdin);
freopen("car.out", "w", stdout);
scanf("%s",str);
int ans=1,l,r;
for (int i=0;i<=5; ++i)
for (int j = i;j<=5; ++j)
if (check(i, j) && j-i+1>ans)
ans = j - i + 1,l = i,r = j;
if(ans==1)
cout<<"-1"<<endl;
else
{
cout<<ans<<endl;
for(int i=l;i<=r;i++)
cout<<str[i];
}
fclose(stdin);
fclose(stdout);
}接下来看万恶的T2
- 转盘停车场(circle)
【题目描述】
6Bit 开车来到了一个超大的转盘停车场，这个转盘停车场里可以停满 N 辆汽车，现在有 M 种车辆， 每种车有无数辆。这里的停车管理员有个奇怪的癖好，就是一定要把停车场 N 个车位停满，而且相邻的两 个车位还不能是相同种品牌的车。该转盘的入口为 1 号车位，转一圈后的出口处是 N 号车位，入口和出口 相邻（即 1 号车位和 N 号车位是相邻的）。问，这个停车场可以停出多少种不同方案？答案可能会很大， 最后结果模上 23333333333 输出。
【输入】
一行两个整数 N 和 M。
【输出】
一个对应的方案数。
【输入输出样例】
circle.in circle.out
3 3 6
【数据范围】
对于 20%数据，M = 2。
另有 20%数据，1 <= N,M <= 10。
对于 60%数据，1 <= N,M <= 106。
对于 100%数据，1 <= N,M <= 1012。
【样例解释】 样例中有三个停车位和三种车的品牌：奥迪、奔驰、宝马。 按照【入口~出口】顺序停车，有 6 种停车方案，方案如下：
奥迪、奔驰、宝马；
奥迪、宝马、奔驰；
奔驰、奥迪、宝马；
奔驰、宝马、奥迪；
宝马、奥迪、奔驰；
宝马、奔驰、奥迪。
话说30分送分我竟然没拿….
伤心ing….
理论上像圆盘染色一样的递推是正确的
实际上只有50分
过分！！！
没办法；（？？？？？？‘；’）
只能强硬的矩阵乘法
随便你什么矩阵乘法
自己去研究
（我错了….代码丢给你们….各位看官相信你们一定能明白我的代码）
#include <stdio.h>
long long mo=23333333333ll;
long long M(long long x,long long y)
{
if(y==0) return 0;
long long m=M(x,y/2);
if(y%2==0) return 2*m%mo;
else return (2*m%mo+x)%mo;
}
struct Matrix
{
long long a[2][2];
};
Matrix I,F,G;
Matrix Cheng(Matrix A,Matrix B)
{
Matrix C;
C.a[0][0]=(M(A.a[0][0],B.a[0][0])+M(A.a[0][1],B.a[1][0]))%mo;
C.a[0][1]=(M(A.a[0][0],B.a[0][1])+M(A.a[0][1],B.a[1][1]))%mo;
C.a[1][0]=(M(A.a[1][0],B.a[0][0])+M(A.a[1][1],B.a[1][0]))%mo;
C.a[1][1]=(M(A.a[1][0],B.a[0][1])+M(A.a[1][1],B.a[1][1]))%mo;
return C;
}
Matrix Quick(Matrix A,long long x)
{
if(x==0) return I;
Matrix B=Quick(A,x/2);
if(x%2==0) return Cheng(B,B);
else return Cheng(Cheng(B,B),A);
}
int main()
{
freopen("circle.in","r",stdin);
freopen("circle.out","w",stdout);
long long n,m;
scanf("%I64d%I64d",&n,&m);
if(n==1)
printf("%I64d",m);
else
{
I.a[0][0]=1,I.a[0][1]=0,I.a[1][0]=0,I.a[1][1]=1;
F.a[0][0]=M(m,m-1),F.a[0][1]=M(M(m,m-1),m-2);
G.a[0][0]=0,G.a[0][1]=m-1,G.a[1][0]=1,G.a[1][1]=m-2;
Matrix S=Cheng(F,Quick(G,n-3));
printf("%I64d",S.a[0][1]);
}
}写的很不开心 不过还是希望各位用operator
方便第一
对了还有我自己写的矩阵快速幂
没用的原因是太懒
各位可以用来优化代码
Matrix operator *(Matrix a,Matrix b)/*operator 重载运算符*/
{
Matrix c(a.n,b.m);
{
for(int i=0;i<a.n;i++)
{
for(int j=0;j<b.m;j++)
{
for(int k=0;k<a.m;k++)
{
(c.a[i][j]+=a.a[i][k]+b.a[k][j]%mod)%=mod;
}
}
}
}
return c;
}
Matrix pow(Matrix a,ll x)/*矩阵快速幂*/
{
Matrix res(a.n,a.m);
for(int i=0;i<a.n;i++)
{
res.a[i][i]=1;
}
for(;x;x>>=1,a=a*a)
{
if(x&1)
res=res*a;
}
return res;
}T3T3T3
- 货物搬运工(goods)
【题目描述】
6Bit 把车停好下车后碰到了一个物流公司正在装运货物，大货车最高承载为 W，总共有 N 件货物，每
件货物有一个重量 Wi，每件货物都有对应的价值 Ci，老板准备去请一个搬运工，去把这些货物搬到货车上， 但想让货车所承载的价值尽可能的高，现在老板应该请一个臂力多大的搬运工才可以呢？当搬运工的臂力 小于物品重量时，则搬不动该物品，无法将此物品搬上大货车。
请你帮忙求一下，如果要使货车所承载的货物价值最高，则搬运工的臂力最小不能小于多少？
【输入】
第一行两个整数 N、W（表示总共有 N 件货物，货车最多可以的承重是 W）。
接下来有 N 行，每行两个整数 Wi、Ci，表示第 i 个货物的重量是 Wi、价值是 Ci。
【输出】 输出一个整数，表示如果要使货车所承载的货物价值最高，则搬运工的最小臂力。
【输入输出样例】
goods.in goods.out
4 100 50
80 100
50 60
50 50
40 40
【数据范围】
对于 20%的数据， N 。
对于 50% 的数据，N <= 100i 。
∑ i=1 W ≤ W
对于 100%的数据，1 <= N <= 103，1 <= W <= 104，1 <= Wi <= W，0 <= Ci <= 105。
【样例解释】 搬运第 2、3 号物品到货车上价值为 110 最高，如果搬运 2、3 号货物，要求搬运工的最小臂力为 50
才可以。
01背包实在是太明显了、
但是这个最小臂力实在是太坑人了…..
CRH提议用裸二分
本人是十分zici的
毕竟是一种方法么
但是
时间要好久啊…
0.98s的成绩我等都看呆了
……………
哇哇哇哇哇
llq提出排序后二分序号..
0.93s
本人实地考察
较优的有在读入后维护一下数组
先按v排序
V相同按价值排序
01的是后用数组存起到达第i种物品时的最大价值
01结束之后 还需要Oans找一下到达第几种方法时能达到这个价值
最后输出该物品的体积…
即使这样 轻松的过了有没有
….
当然你也可以直接扔到01里去找这个东西；（记性呢）
代码在下面
#include <bits/stdc++.h>
using namespace std;
pair <int ,int >p[10001];
int f[10000];
int aa[10001];
int main()
{
// freopen("goods.in","r",stdin);
// freopen("goods.out","w",stdout);
int n;
int w;
cin>>n>>w;
for(int i=1;i<=n;i++)
cin>>p[i].first>>p[i].second;
for(int i=1;i<=n;i++)
{
for(int j=w;j>=p[i].first;j--)
{
f[j]=max(f[j],f[j-p[i].first]+p[i].second);
}
for(int j=0;j<=w;j++)
{
aa[i]=max(aa[i],f[j]);
}
}
for(int i=1;i<=n;i++)
{
if(aa[i]==aa[n])
{
cout<<p[i].first;
return 0;
}
}
}上面的是最后一种做法
下面的是二分
（感谢CRh提供该代码）
熇姐姐的代码还是正常人能看懂的
不像我的 ……..
#include<stdio.h>
#include<string.h>
int max(int a,int b)
{
if(a>b)return a;
return b;
}
int min(int a,int b)
{
if(a>b)return b;
return a;
}
int maxc,n,we;
int w[1005];
int c[1005];
int f[10005];
int judge(int x)
{
memset(f,0,sizeof(f));
for(int i = 1;i<= n;i++)
{
for(int j = we;j>=w[i];j--)
{
if(f[j-w[i]]+c[i]>f[j]&&w[i]<=x)
{
f[j] = f[j-w[i]]+c[i];
}
}
}
return f[we];
}
int main()
{
freopen("goods.in","r",stdin);
freopen("goods.out","w",stdout);
scanf("%d%d",&n,&we);
int l = 0x7f;
int r = 0;
for(int i = 1;i<= n;i++)
{
scanf("%d%d",&w[i],&c[i]);
l = min(l,w[i]);
r = max(r,w[i]);
}
for(int i = 1;i<= n;i++)
{
for(int j = we;j>= w[i];j--)
{
f[j] = max(f[j],f[j-w[i]]+c[i]);
}
}
maxc = f[we];
r = r+1;
while(l<r)
{
int mid = (l+r)>>1;
if(judge(mid)<maxc)l = mid+1;
else r = mid;
}
printf("%d",l);
return 0;
}好棒好棒….
又过去一次考试….
话说下一次好快就要到了…….
没办法….3.
233333333333333333333333333333333333333333333333
下次见