首页 > 代码库 > HDU 4028 The time of a day（动态规划）

HDU 4028 The time of a day（动态规划）

2024-07-17 04:09:56   223人阅读

The time of a day

Problem Description
There are no days and nights on byte island, so the residents here can hardly determine the length of a single day. Fortunately, they have invented a clock with several pointers. They have N pointers which can move round the clock. Every pointer ticks once per second, and the i-th pointer move to the starting position after i times of ticks. The wise of the byte island decide to define a day as the time interval between the initial time and the first time when all the pointers moves to the position exactly the same as the initial time.
The wise of the island decide to choose some of the N pointers to make the length of the day greater or equal to M. They want to know how many different ways there are to make it possible.
 

Input
There are a lot of test cases. The first line of input contains exactly one integer, indicating the number of test cases.
  For each test cases, there are only one line contains two integers N and M, indicating the number of pointers and the lower bound for seconds of a day M. (1 <= N <= 40, 1 <= M <= 263-1)
 

Output
For each test case, output a single integer denoting the number of ways.
 

Sample Input
3
5 5
10 1
10 128
 

Sample Output
Case #1: 22
Case #2: 1023
Case #3: 586
 

Source
The 36th ACM/ICPC Asia Regional Shanghai Site —— Online Contest
 

Recommend
lcy   |   We have carefully selected several similar problems for you:  4027 4022 4023 4021 4029 
 


题目大意：

有n组测试数据，接下来n和m，n表示n个指针1~n，分别是 k 下回到起点，问你从n个选出任意多个指针，同时停在起点算1天，1天的时间超过m的方案有多少种？

解题思路：

动态规划，状态较分散，所以用Map离散化。


解题代码：

#include <iostream>
#include <cstdio>
#include <map>
#include <set>
using namespace std;

map <int,multiset<int> > mpx;
map <int,multiset<int> > mpy;
int n,m;

int main(){
    int a,c;
    while(scanf("%d%d",&n,&m)!=EOF && (m||n) ){
        mpx.clear();
        mpy.clear();
        for(int i=0;i<n;i++){
            scanf("%d%d",&a,&c);
            mpx[a].insert(c);
            mpy[c].insert(a);
        }
        for(int i=0;i<m;i++){
            scanf("%d%d",&a,&c);
            if(a==0){
                printf("%d\n",mpx[c].size() );
                for(multiset<int>::iterator it=mpx[c].begin();it!=mpx[c].end();it++){
                    int y=(*it);
                    mpy[y].erase(mpy[y].find(c));
                }
                mpx[c].clear();
            }else{
                printf("%d\n",mpy[c].size() );
                for(multiset<int>::iterator it=mpy[c].begin();it!=mpy[c].end();it++){
                    int x=(*it);
                    mpx[x].erase(mpx[x].find(c));
                }
                mpy[c].clear();
            }
        }
        printf("\n");
    }
    return 0;
}







联系
我们