ブルーブリッジカップ冬休みトレーニング----9

14605 ワード
C++プログラミング
バイオリンの音は1本の川のようで、左岸は私の忘れられない思い出で、右岸は私が握る価値のあるきらきら光る年华で、中间に流れているのは、私の年々の淡い感伤です.
                                                 A - Charm Bracelet
Bessie has gone to the mall's jewelry store and spies a charm bracelet. Of course, she'd like to fill it with the best charms possible from the N (1 ≤ N ≤ 3,402) available charms. Each charm i in the supplied list has a weight Wi (1 ≤ Wi ≤ 400), a 'desirability' factor Di (1 ≤ Di ≤ 100), and can be used at most once. Bessie can only support a charm bracelet whose weight is no more than M (1 ≤ M ≤ 12,880).
Given that weight limit as a constraint and a list of the charms with their weights and desirability rating, deduce the maximum possible sum of ratings.
Input
* Line 1: Two space-separated integers: N and M * Lines 2..N+1: Line i+1 describes charm i with two space-separated integers: Wi and Di
Output
* Line 1: A single integer that is the greatest sum of charm desirabilities that can be achieved given the weight constraints
Sample Input 
4 6
1 4
2 6
3 12
2 7

Sample Output 
23
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#define inf 0x3f3f3f3f
typedef long long ll;
using namespace std;
int m,n,w[5005],d[5005],dp[20000];
int main()
{
    while(scanf("%d %d",&n,&m)!=EOF)
    {
        memset(dp,0,sizeof(dp));
        for(int i=0; i=w[i]; j--)
                dp[j]=max(dp[j],dp[j-w[i]]+d[i]);
        printf("%d
",dp[m]);
    }
    return 0;
}

                                             B - Catch That Cow
Farmer John has been informed of the location of a fugitive cow and wants to catch her immediately. He starts at a point N (0 ≤ N ≤ 100,000) on a number line and the cow is at a point K (0 ≤ K ≤ 100,000) on the same number line. Farmer John has two modes of transportation: walking and teleporting.
* Walking: FJ can move from any point X to the points X - 1 or X + 1 in a single minute * Teleporting: FJ can move from any point X to the point 2 × X in a single minute.
If the cow, unaware of its pursuit, does not move at all, how long does it take for Farmer John to retrieve it?
Input
Line 1: Two space-separated integers: N and K
Output
Line 1: The least amount of time, in minutes, it takes for Farmer John to catch the fugitive cow.
Sample Input 
5 17

Sample Output 
4

Hint
The fastest way for Farmer John to reach the fugitive cow is to move along the following path: 5-10-9-18-17, which takes 4 minutes. 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#define inf 0x3f3f3f3f
typedef long long ll;
using namespace std;
int n,k,jg,bs[100010],vis[100010];
queueq;
void bfs()
{
    int a, b;
    q.push(n);
    bs[n]=0;
    vis[n]=1;
    while(!q.empty())
    {
        a=q.front();
        q.pop();
        for(int i=0; i<3; i++)
        {
            if(i==0)
                b=a*2;
            if(i==1)
                b=a+1;
            if(i==2)
                b=a-1;
            if(b<0 || b>100000)
                continue;
            if(!vis[b])
            {
                q.push(b);
                bs[b]=bs[a]+1;
                vis[b]=1;
            }
            if(b==k)
                jg=bs[b];
        }
    }
}
int main()
{
    scanf("%d%d",&n,&k);
    if(n>=k)
        jg=n-k;
    else
        bfs();
    printf("%d
", jg);
    return 0;
}

                                                 C - Best Cow Line
FJ is about to take his N (1 ≤ N ≤ 2,000) cows to the annual"Farmer of the Year"competition. In this contest every farmer arranges his cows in a line and herds them past the judges.
The contest organizers adopted a new registration scheme this year: simply register the initial letter of every cow in the order they will appear (i.e., If FJ takes Bessie, Sylvia, and Dora in that order he just registers BSD). After the registration phase ends, every group is judged in increasing lexicographic order according to the string of the initials of the cows' names.
FJ is very busy this year and has to hurry back to his farm, so he wants to be judged as early as possible. He decides to rearrange his cows, who have already lined up, before registering them.
FJ marks a location for a new line of the competing cows. He then proceeds to marshal the cows from the old line to the new one by repeatedly sending either the first or last cow in the (remainder of the) original line to the end of the new line. When he's finished, FJ takes his cows for registration in this new order.
Given the initial order of his cows, determine the least lexicographic string of initials he can make this way.
Input
* Line 1: A single integer: N * Lines 2..N+1: Line i+1 contains a single initial ('A'..'Z') of the cow in the ith position in the original line
Output
The least lexicographic string he can make. Every line (except perhaps the last one) contains the initials of 80 cows ('A'..'Z') in the new line.
Sample Input 
6
A
C
D
B
C
B

Sample Output 
ABCBCD
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#define inf 0x3f3f3f3f
typedef long long ll;
using namespace std;
char s[2010];
int n,ct;
int main()
{
    cin>>n;
    getchar();
    for(int i=0; i>s[i];
    int i=0,j=n-1;
    while(i<=j)
    {
        int fg=0;
        for(int k=0; i+ks[j-k])
            {
                fg=0;
                break;
            }
        }
        ct++;
        if(fg==1)
            cout<

                                             D - Cleaning Shifts
Farmer John is assigning some of his N (1 <= N <= 25,000) cows to do some cleaning chores around the barn. He always wants to have one cow working on cleaning things up and has divided the day into T shifts (1 <= T <= 1,000,000), the first being shift 1 and the last being shift T.  Each cow is only available at some interval of times during the day for work on cleaning. Any cow that is selected for cleaning duty will work for the entirety of her interval.  Your job is to help Farmer John assign some cows to shifts so that (i) every shift has at least one cow assigned to it, and (ii) as few cows as possible are involved in cleaning. If it is not possible to assign a cow to each shift, print -1.
Input
* Line 1: Two space-separated integers: N and T  * Lines 2..N+1: Each line contains the start and end times of the interval during which a cow can work. A cow starts work at the start time and finishes after the end time.
Output
* Line 1: The minimum number of cows Farmer John needs to hire or -1 if it is not possible to assign a cow to each shift.
Sample Input 
3 10
1 7
3 6
6 10

Sample Output 
2

Hint
This problem has huge input data,use scanf() instead of cin to read data to avoid time limit exceed.  INPUT DETAILS:  There are 3 cows and 10 shifts. Cow #1 can work shifts 1..7, cow #2 can work shifts 3..6, and cow #3 can work shifts 6..10.  OUTPUT DETAILS:  By selecting cows #1 and #3, all shifts are covered. There is no way to cover all the shifts using fewer than 2 cows. 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#define inf 0x3f3f3f3f
typedef long long ll;
using namespace std;
int t,n;
struct node
{
    int x;
    int y;
} p[25010];
bool cmp(node a,node b)
{
    if(a.x==b.x)
        return a.y>n>>t;
    for(int i=0; i>p[i].x>>p[i].y;
    sort(p,p+n,cmp);
    if(p[0].x==1&&p[0].y>=t)
        cout<<1<m+1)
            {
                cout<=t)
                break;
        }
        if (m

                                   E - Ping-Pong (Easy Version)
In this problem at each moment you have a set of intervals. You can move from interval (a, b) from our set to interval (c, d) from our set if and only if c a d or c b d. Also there is a path from interval I1from our set to interval I2 from our set if there is a sequence of successive moves starting from I1 so that we can reach I2.
Your program should handle the queries of the following two types:
  • "1 x y" (x y) — add the new interval (x, y) to the set of intervals. The length of the new interval is guaranteed to be strictly greater than all the previous intervals.
  • "2 a b" (a ≠ b) — answer the question: is there a path from a-th (one-based) added interval to b-th (one-based) added interval?

    • Answer all the queries. Note, that initially you have an empty set of intervals.
    Input
    The first line of the input contains integer n denoting the number of queries, (1 ≤ n ≤ 100). Each of the following lines contains a query as described above. All numbers in the input are integers and don't exceed 109 by their absolute value.
    It's guaranteed that all queries are correct.
    Output
    For each query of the second type print "YES"or "NO"on a separate line depending on the answer.
    Examples
    Input 
    5
1 1 5
1 5 11
2 1 2
1 2 9
2 1 2

    Output 
    NO
YES
    #include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#define inf 0x3f3f3f3f
typedef long long ll;
using namespace std;
int x,y,n,vis[1010],jg,ct=1,k;
struct node
{
    int l;
    int r;
} p[1010];
int check(int a, int b)
{
    if (p[a].l>p[b].l&&p[a].l
    p[b].l&&p[a].r
    >n;
    while(n--)
    {
        cin>>k;
        if(k==1)
        {
            cin>>p[ct].l>>p[ct].r;
            ct++;
        }
        else
        {
            cin>>x>>y;
            for(int i=0; i

    G-円滑工事
    ある省は都市交通状況を調査し、既存の都市道路統計表を得て、各道路が直接つながっている都市をリストした.省政府の「円滑な工事」の目標は、全省のどの2つの都市間でも交通を実現させることである(ただし、直接的な道路がつながっているとは限らず、互いに間接的に道路を通過すればよい).最低でも何本の道路を建設する必要がありますか? 
    Input
    テスト入力には、いくつかのテスト例が含まれます.各試験例の第1行は、都市数N(<1000)と道路数Mの2つの正の整数を与える.その後のM行はM道に対応し、各行は正の整数のペアを与え、それぞれこの道が直接つながっている2つの町の番号である.簡単にするために、町は1からN番までです.注意:2つの都市の間には複数の道路が通じることができ、すなわち3 3 3 1 2 2 1という入力も合法的であり、Nが0の場合、入力が終了し、この例は処理されない. 
    Output
    各試験例に対して,1行で最低でも建設が必要な道路数を出力する. 
    Sample Input 
    4 2
1 3
4 3
3 3
1 2
1 3
2 3
5 2
1 2
3 5
999 0
0

    Sample Output 
    1
0
2
998    
  
Huge input, scanf is recommended.

    Hint 
    Hint
    #include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#define inf 0x3f3f3f3f
typedef long long ll;
using namespace std;
int gj[1010];
int fd(int x)
{
    if(gj[x]==x)
        return x;
    return gj[x]=fd(gj[x]);
}
void hb(int a,int b)
{
    int aa=fd(a);
    int bb=fd(b);
    if(aa!=bb)
        gj[bb]=aa;
}
int main()
{
    int n,m,i,x,y;//n    ，m    
    while(scanf("%d%d",&n,&m)&&n!=0)
    {
        int jg=0;
        for(i=1; i<=n; i++)
            gj[i]=i;
        for(i=0; i

    Veeプロジェクトにserviceworkerを追加
    更新の瞬間にスタイルがロードされていないか、VUEコードが発生する問題を解決する方法