Hdu 2845 Beans
链接
Beans
题意
给定M*N的矩阵，每个格有一颗豆，其品质为Aij。
规则：若吃豆(x,y)，则不能吃(x,y-1)和(x,y+1),也不能吃x-1行和x+1行的豆
问最多能吃到多少品质的豆？
分析
先dp求出每一行能吃到的最大值，再在行上进行dp
dp[i]=max{dp[i-1],dp[i-2]+a[i]}
参考代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
| #include<stdio.h>
#include<string.h>
#define max(a,b) a>b?a:b
const int N=200010;
int dp[N],row[N],a[N];
int main()
{
int n,m;
while(scanf("%d%d",&n,&m)!=EOF){
memset(row,0,sizeof(row));
dp[0]=0;
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
scanf("%d",&a[j]);
if(j==1)
dp[j]=a[j];
else
dp[j]=max(dp[j-2]+a[j],dp[j-1]);
row[i]=max(row[i],dp[j]);
}
}
int ans=0;
for(int i=1;i<=n;i++){
if(i==1)
dp[i]=row[i];
else
dp[i]=max(dp[i-2]+row[i],dp[i-1]);
ans=max(ans,dp[i]);
}
printf("%d\n",ans);
}
return 0;
}
|
Hdu 2846 Repository
链接
Repository
题意
已知p个商品名字,有q个询问，每次查询一个串，问它是多少个商品名字的字串
分析
AC自动机
将q次询问的串建树，然后对每一个商品名字进行匹配，注意查询中可能有重复的串
参考代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
| #include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<queue>
#include<map>
#include<string>
const int N=100010;
using namespace std;
char name[10010][30];
typedef struct stu{
struct stu* next[26];
struct stu* fail;
int cnt;
}Node;
bool flag[N];
int ans[N],num[N];
map<string,int> mp;
Node* createNode()
{
Node* p=(Node*)malloc(sizeof(Node));
memset(p->next,0,sizeof(p->next));
p->fail=NULL;
p->cnt=0;
return p;
}
void insertNode(Node* root,char s[],int cnt)
{
int pos=0;
Node* p=root;
while(s[pos]!='\0'){
int id=s[pos]-'a';
if(p->next[id]==NULL){
p->next[id]=createNode();
}
p=p->next[id];
pos++;
}
p->cnt=cnt;
}
void buildFail(Node* root)
{
queue<Node*> q;
q.push(root);
while(!q.empty()){
Node* p=q.front();
q.pop();
for(int i=0;i<26;i++){
if(p->next[i]==NULL)
continue;
if(p==root)
p->next[i]->fail=root;
else{
Node *temp=p->fail;
while(temp!=NULL){
if(temp->next[i]!=NULL){
p->next[i]->fail=temp->next[i];
break;
}
temp=temp->fail;
}
if(temp==NULL)
p->next[i]->fail=root;
}
q.push(p->next[i]);
}
}
}
void searchNode(Node* root,char str[])
{
Node* p=root;
int pos=0;
memset(flag,0,sizeof(flag));
while(str[pos]!='\0'){
int id=str[pos]-'a';
while(p->next[id]==NULL&&p!=root)
p=p->fail;
p=p->next[id];
if(p==NULL)
p=root;
Node* temp=p;
while(temp!=root&&temp->cnt!=-1){
if(!flag[temp->cnt]){
ans[temp->cnt]++;
flag[temp->cnt]=true;
}
temp=temp->fail;
}
pos++;
}
}
int main()
{
int p;
while(scanf("%d",&p)!=EOF){
Node* root=createNode();
for(int i=1;i<=p;i++)
scanf("%s",name[i]);
int q;
scanf("%d",&q);
mp.clear();
for(int i=1;i<=q;i++){
num[i]=i;
char str[30];
scanf("%s",str);
string tmp=str;
if(!mp[tmp]){
mp[tmp]=i;
insertNode(root,str,i);
}
else{
num[i]=mp[tmp];
}
}
buildFail(root);
memset(ans,0,sizeof(ans));
for(int i=1;i<=p;i++)
searchNode(root,name[i]);
for(int i=1;i<=q;i++)
printf("%d\n",ans[num[i]]);
}
return 0;
}
|
Hdu 2847 Binary String
链接
Binary String
题意
给定一个二进制串s和数k,可在s的任意位置添加0或1得到串t,求能被k整除的最小串s（数值最小)
分析
可从小到大枚举k的倍数，其二进制串t,若给定的二进制串s是t的子序列，则可通过添加0或1得到，即满足条件
参考代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
| #include<stdio.h>
#include<string.h>
char s[35],t[35];
void binary(int n)
{
if(n==0){
t[0]='0';
t[1]=0;
return ;
}
int cnt=0;
while(n){
t[cnt++]=(n&1)+'0';
n>>=1;
}
t[cnt]=0;
for(int i=0;i<cnt/2;i++){
char tmp=t[i];
t[i]=t[cnt-1-i];
t[cnt-1-i]=tmp;
}
}
int decimal()
{
int n=0;
for(int i=0;s[i]!='\0';i++)
n=n*2+(s[i]-'0');
return n;
}
bool judge()
{
int n=strlen(s);
int m=strlen(t);
int pos=0;
for(int i=0;i<m;i++){
if(pos<n&&s[pos]==t[i])
pos++;
}
if(pos==n)
return true;
return false;
}
int main()
{
int k;
while(scanf("%s%d",s,&k)!=EOF){
int n=decimal();
for(int i=n/k;;i++){
int now=i*k;
binary(now);
if(judge())
break;
}
printf("%s\n",t);
}
return 0;
}
|
Hdu 2850 Load Balancing
链接
Load Balancing
题意
有n个任务，m个服务器，每个任务工作时间为ti，现需给每个任务分配一个服务器，使得负载平衡最小
负载平衡：max{Ti}-min{Tj},Ti为第i个服务器完成任务的总时间
分析
贪心
将任务按工作时间从大到小排序，每次优先将任务分给服务器工作时间小的服务器，用优先队列实现
参考代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
| #include<stdio.h>
#include<queue>
#include<algorithm>
#include<string.h>
const int N=100010;
typedef long long LL;
using namespace std;
struct stu{
int id;
LL val;
bool operator >(const stu& x) const
{
return val>x.val;
}
};
priority_queue<stu,vector<stu>,greater<stu> > q;
struct stu job[N];
int ans[N];
bool cmp(stu a,stu b)
{
return a.val>b.val;
}
void init(int n,int m)
{
while(!q.empty()){
q.pop();
}
struct stu tmp;
tmp.val=0;
for(int i=0;i<m;i++){
tmp.id=i;
q.push(tmp);
}
sort(job+1,job+1+n,cmp);
}
int main()
{
int T;
scanf("%d",&T);
while(T--){
int n,m;
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++){
scanf("%lld",&job[i].val);
job[i].id=i;
}
init(n,m);
for(int i=1;i<=n;i++){
struct stu tmp=q.top();
q.pop();
tmp.val+=job[i].val;
ans[job[i].id]=tmp.id;
q.push(tmp);
}
printf("%d\n",n);
for(int i=1;i<=n;i++){
printf("%d",ans[i]);
if(i!=n)
printf(" ");
else
printf("\n");
}
}
return 0;
}
|
Hdu 2851 Lode Runner
链接
Lode Runner
题意
有n条水平的路，起点Si,终点Ei,危险度Wi,路的终点递增。每条路的右侧有一个垂直的无限长的梯子，梯子穿过或紧挨第i条路，则可通过梯子到达第i条路。现要从起点（第1条路）分别到达一些目的地，问危险最少是多少？
分析
设dp[i]到达第i条路的最小危险度，dp[1]=W[1];
若Si<=Sj 且 Ej<=Ei，则可从i到j,dp[j]=min(dp[j],dp[i]+W[j]);
参考代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
| #include<stdio.h>
#include<string.h>
const int N=2010;
const int INF=9999999;
#define min(a,b) a<b?a:b
struct stu{
int st,ed;
int w;
}a[N];
int dp[N];
int main()
{
int T;
scanf("%d",&T);
while(T--){
int n,m;
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++){
scanf("%d%d%d",&a[i].st,&a[i].ed,&a[i].w);
dp[i]=INF;
}
dp[1]=a[1].w;
for(int i=1;i<n;i++){
for(int j=i+1;j<=n;j++){
if(a[i].ed>=a[j].st)
dp[j]=min(dp[j],dp[i]+a[j].w);
}
}
for(int i=1;i<=m;i++){
int x;
scanf("%d",&x);
if(dp[x]==INF)
dp[x]=-1;
printf("%d\n",dp[x]);
}
}
return 0;
}
|
Hdu 2852 KiKi’s K-Number
链接
KiKi’s K-Number
题意
三种操作：
0 a:向容器加入一个数a
1 a:从容器删除一个数a,若a不存在，输出”No Elment!”
2 a k:查询比第k个比a大的数，若存在，则输出该数，否则输出”Not Find!”
分析
树状数组+二分查找
query(x):不大于x数的个数，总数减query(x)：大于x的个数
参考代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
| #include<stdio.h>
#include<string.h>
const int N=100010;
#define max(a,b) a>b?a:b
int c[N];
int lowbit(int x)
{
return x&(-x);
}
void update(int pos,int val)
{
for(int i=pos;i<N;i+=lowbit(i)){
c[i]+=val;
}
}
int query(int pos)
{
int sum=0;
for(int i=pos;i>=1;i-=lowbit(i)){
sum+=c[i];
}
return sum;
}
int binSearch(int a,int k,int r)
{
int l=1;
int num=query(a);
while(l<r){
int mid=(l+r)>>1;
if(query(mid)-num<k)
l=mid+1;
else
r=mid;
}
return r;
}
int main()
{
int m;
while(scanf("%d",&m)!=EOF){
memset(c,0,sizeof(c));
int maxn=-1;
for(int i=0;i<m;i++){
int ope,a,k;
scanf("%d",&ope);
if(ope==0){
scanf("%d",&a);
update(a,1);
maxn=max(maxn,a);
}
else if(ope==1){
scanf("%d",&a);
if(query(a)-query(a-1)==0)
printf("No Elment!\n");
else
update(a,-1);
}
else{
scanf("%d%d",&a,&k);
int sum=query(maxn)-query(a);
if(sum<k){
printf("Not Find!\n");
continue;
}
int ans=binSearch(a,k,maxn);
printf("%d\n",ans);
}
}
}
return 0;
}
|