时间限制: 1 Sec 内存限制: 128 MB

提交 状态 题面

题目描述

In 1736, Leonhard Euler wrote a paper on the Seven Bridges of Königsberg which is regarded as the first paper in the history of graph theory. Nowadays, the study of graph theory is considered very important as indicated by the fact that most textbooks in discrete mathematics have a chapter on graph theory.

This problem is related to graph theory, especially on tree and forest. Given N tuples (ui,vi,wi), your task is to construct a forest with a minimum number of trees which satisfies the following seven requirements:

1. Each tree in the forest is a rooted tree;
2. Each node x in the forest has a value x.A;
3. Each edge (x, y) in the forest has a value (x, y).B;
4. Each tuple (ui,vi,wi) appears exactly once in the forest as two nodes with a parent-child relationship (parent node p and child node c) where: ui = p.A, vi = c.A, and wi = (p, c).B;
5. For any non-root and non-leaf node x in the forest, (p, x).B is smaller than any (x, c).B, where p is x’s parent and c is x’s child;
6. All nodes in the forest have at most M children.
7. The forest should contain exactly N edges.

To simplify the problem, it is guaranteed that wi in any tuple is unique, i.e. no two tuples with the same wi .

Output the number of trees in such forest (the forest should have the minimum number of trees).

输入

The first line contains two integers: N M(1 ≤ N,M ≤ 100,000) in a line denoting the number of tuples and the maximum number of children for each node in the forest. The next N following lines, each contains three integers: ui vi wi (1 ≤ ui,vi ≤ 2,000,000,000; 1 ≤ wi ≤ N ) in a line denoting the tuple (ui,vi,wi). It is guaranteed that there will be no two tuples with the same wi .

输出

The output contains an integer denoting the number of trees in a forest with a minimum number of trees which satisfies the given requirements, in a line.

样例输入

5 2

2 4 3

4 4 5

4 7 1

7 2 4

4 8 2

样例输出

2

提示

For the sample, this forest is the only forest which satisfies all the requirements. There are 2 trees in this forest.

On the other hand, this forest does not satisfy the requirements due to:

1. Node b violates requirement #5 as (a,b).B = 3 is larger than (b,c).B = 1 and (b,d).B = 2.
2. Node b violates requirement #6 as it has 3 children (note that M is 2).
3. There are 6 edges in the forest while ! = 5 (violates requirement #7).

Note that violating even one requirement already makes the forest invalid.

#pragma GCC optimize(3,"Ofast","inline")
#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int N=2e5+10;
struct  node
{
    int u,v,w;
}G[N];
int n,m;
unordered_map<int,int>mp;
bool cmp(node a,node b)
{
    return  a.w<b.w;
}
int main()
{
    scanf ("%d%d",&n,&m);
    for(int i=0;i<n;i++)
    {
        int u,v,w;
        scanf ("%d%d%d",&G[i].u,&G[i].v,&G[i].w);
    }
    sort(G,G+n,cmp);
    int ans=0;
    for(int i=0;i<n;i++)
    {
        int u=G[i].u,v=G[i].v;
        if(!mp[u])
        {
            ans++;
            mp[u]+=m;
        }
        mp[u]--;
        mp[v]+=m;
    }
    printf ("%d\n",ans);
}

时间限制: 1 Sec 内存限制: 128 MB

提交 状态 题面

题目描述

Romanos: “Can I submit an interactive problem to ACM-ICPC 2017 Jakarta?”

Theodora: “No.”

Romanos: “Aww, man.. That’s not fun.”

Then Romanos decided to submit a non-interactive version of his problem to the contest; and here it is, based on his playing with Theodora.

Romanos and Theodora are playing a game. Initially, Theodora picks a number between 1 to N inclusive. Romanos’ goal is to determine that number. He can make up to ! guesses. For each guess, he will say a number out loud as his guess. Theodora will then say one of the following answers based on the exact condition:

• “My number is smaller than your guess (<)”,

• “My number is greater than your guess (>)”, or

• “Your guess is correct (=)”.

The game will end right after one of the following:

• Romanos guesses the correct number (he wins), or

• All ! guesses are wrong (he loses).

Sadly, Romanos is not playing the game seriously. He knows the best strategy to win this game, but he does not always use it. Nevertheless, he pretends that he plays seriously, hence his guess will never be a dumb one. In other words, his guess will always be a number between 1 to N inclusive and will always be consistent with all of Theodora’s previous answers.

For example, suppose N is 10 and Romanos’ first guess is 4. If Theodora answers “My number is smaller than your guess (<)” then the next Romanos’s guess will always be between 1 to 3, inclusive.

Contrast to Romanos, Theodora is playing the game too seriously. She wants to win (by making Romanos lose) and “cheats” as follows.

Adaptively, Theodora might change her number as far as it is consistent with all of her previous answers. To do that, whenever possible, Theodora will always answer either “My number is smaller than your guess (<)” or “My number is greater than your guess (>)” that maximizes the possible answer range. In the case of tie, she will always answer the first one (<).

For example, suppose N is 10 and Romanos’ first guess is 4. Theodora will always answer “My number is greater than your guess (>)” because the possible answer range will be between 5 to 10 inclusive; it is larger than 1 to 3 inclusive.

Now, this is the actual problem proposed by Romanos. You are given N,K , and Theodora’s answer for each guess. Can you show one of the possible scenario for Romanos’ guesses or state that it is impossible?

输入

The first line contains two integers: N K(1 ≤N≤ 1018; 1 ≤K≤ 50,000) in a line denoting the number range and the number of guesses. The second line contains a string in a line denoting Theodora’s answers. Each character of the string is either ‘<‘, ‘>’, or ‘=’, and either:

• The last character of the string is ‘=’ and each character of the string other than the last character is either ‘<‘ or ‘>’, and the length of the string is not more than K , or

• The length of the string is exactly K and each character of the string is either ‘<‘ or ‘>’.

输出

If there is a possible scenario for Romanos’ guesses,output YES，else output NO.

样例输入

10 5

><>=

样例输出

YES

#include<iostream>
#include<cstring>
#include<string>
#include<cstdio>
#include<algorithm>
#define ll long long
using namespace std;
const int inf = 0x3f3f3f3f;
const int maxn=5e4+10;
ll num;
ll n,k;
char op[maxn];
int judge(ll l,ll r,int p){
    int cnt=0;
    while(l<r){
        //cout<<l<<"   "<<r<<endl;
        if(op[p]=='=') break;
        cnt++;
        ll mid=(l+r)>>1;
        if((r-l+1)&1){
            if(op[p]=='>') l=mid;
            else r=mid-1;
        }
        else{
            if(op[p]=='>') l=mid+1;
            else r=mid;
        }
        p++;
        if(p>num) break;
    }
    //cout<<l<<" "<<r<<endl;
    if(l<r) return inf;
    //cout<<cnt<<endl;
    return cnt;
}
bool check(){
    if(num>n)return false;
    if(k>=n&&op[n]!='=') return false;
    if(op[num]=='='&&num<judge(1ll,n,1)) return false;
    return true;
}
int main()
{
    while(~scanf("%lld %lld",&n,&k)){
        scanf("%s",op+1);
        num=strlen(op+1);
        //cout<<num<<endl;
        if(check()){
            printf("YES\n");
        }
        else{
            printf("NO\n");
        }
    }
}

时间限制: 1 Sec 内存限制: 128 MB

提交 状态 命题人:admin

题目描述

There are N teams (numbered from 1 to N ) and M problems (numbered from 1 to N ) in this year’s ICPC. The j-th problem has Tj testcases. Surprisingly, every team submitted exactly one solution to every problem. The N -th team managed to solve Sij testcases on the N -th problem.

A team solved a problem only if the team managed to solve ALL testcases on that problem. The winning team is the team with the most number of problems solved. If there are more than one team with the most number of problems solved, then the winning team is the team with the smallest index among those teams.

Determine the index of the winning team.

输入

The first line contains two integers: N M (1 ≤ N ,M ≤ 100) in a line denoting the number of teams and the number of problems. The second line contains M integers: T1 T2…TM(0 ≤ Ti ≤ 100) in a line denoting the number of testcases. The next N following lines, each contains M integers; the j-th integer on the i-th line is Sij (0 ≤ Sij ≤ Tj ) denoting the number of solved testcases by the i-th team for the j-th problem.

输出

The output contains the index of the winning team, in a line.

样例输入

3 2

10 20

0 19

10 0

9 19

样例输出

2

提示

On the first sample, the first and the third team did not solve any problem, and the second team solved the first problem. Therefore, the second team is the winner.

#include<iostream>
#include<cstring>
#include<string>
#include<cstdio>
#include<algorithm>
#define ll long long
using namespace std;
const int N=105;
int n,m;
int stand[N];
struct node
{
    int no,sol;
}ans[N];
bool cmp(node a,node b)
{
    if(a.sol!=b.sol) return a.sol>b.sol;
    return  a.no<b.no;
}
int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<=m;i++) scanf("%d",&stand[i]);
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++)
        {
            int temp;
            scanf("%d",&temp);
            if(temp==stand[j]) ans[i].sol++;
        }
        ans[i].no=i;
    }
    sort(ans+1,ans+1+n,cmp);
    printf("%d\n",ans[1].no);
}

时间限制: 1 Sec 内存限制: 128 MB

提交 状态 题面

题目描述

Dave loves strings consisting only of ‘(‘ and ‘)’. Especially, he is interested in balanced strings. Any balanced strings can be constructed using the following rules:

A string “()” is balanced.

Concatenation of two balanced strings are balanced.

If T is a balanced string, concatenation of ‘(‘, T, and ‘)’ in this order is balanced. For example, “()()” and “(()())” are balanced strings. “)(” and “)()(()” are not balanced strings.

Dave has a string consisting only of ‘(‘ and ‘)’. It satises the followings:

You can make it balanced by swapping adjacent characters exactly A times.

For any non-negative integer B (B<A), you cannot make it balanced by B swaps of adjacent characters.

It is the shortest of all strings satisfying the above conditions.

Your task is to compute Dave’s string. If there are multiple candidates, output the minimum in lexicographic order. As is the case with ASCII, ‘(‘ is less than ‘)’.

输入

The input consists of a single test case, which contains an integer A (1≤A≤109).

输出

Output Dave’s string in one line. If there are multiple candidates, output the minimum in lexicographic order.

样例输入

1

样例输出

)(

提示

There are infinitely many strings which can be balanced by only one swap. Dave’s string is the shortest of them.

#include <bits/stdc++.h>
using namespace std;
 
int main()
{
    int a;
    cin>>a;
    int n=int((sqrt (1ll*8*a)-1)*1.0/2);
    int m=n+1;
    if(a==1) {
        printf (")(\n");
    }
    else if(a==2) {
        printf (")()(\n");
    }
    else {
        int cnt=a-n*(n+1)/2;
        int sum=m*2;
        int cnta=m,cntb=m;
        for(int i=1;i<=cnt;i++) printf (")"),sum--,cnta--;
        printf ("(");
        cntb--;
        while (cnta--) {
            printf (")");
        }
        while (cntb--) {
            printf ("(");
        }
        printf ("\n");
    }
    return 0;
}

时间限制: 1 Sec 内存限制: 128 MB

提交 状态 题面

题目描述

You are working for a worldwide game company as an engineer in Tokyo. This company holds an annual event for all the staff members of the company every summer. This year’s event will take place in Tokyo. You will participate in the event on the side of the organizing staff. And you have been assigned to plan a recreation game which all the participants will play at the same time.

After you had thought out various ideas, you designed the rules of the game as below.

Each player is given a positive integer before the start of the game.

Each player attempts to make a pair with another player in this game, and formed pairs compete with each other by comparing the products of two integers.

Each player can change the partner any number of times before the end of the game, but cannot have two or more partners at the same time.

At the end of the game, the pair with the largest product wins the game.

In addition, regarding the given integers, the next condition must be satisfied for making a pair.

The sequence of digits obtained by considering the product of the two integers of a pair as a string must be increasing and consecutive from left to right. For example, 2, 23, and 56789 meet this condition, but 21, 334, 135 or 89012 do not.

Setting the rules as above, you noticed that multiple pairs may be the winners who have the same product depending on the situation. However, you can find out what is the largest product of two integers when a set of integers is given.

Your task is, given a set of distinct integers which will be assigned to the players, to compute the largest possible product of two integers, satisfying the rules of the game mentioned above.

输入

The input consists of a single test case formatted as follows.

N

a1 a2 … aN

The first line contains a positive integer N which indicates the number of the players of the game. N is an integer between 1 and 1,000. The second line has N positive integers that indicate the numbers given to the players. For i=1,2,…,N−1, there is a space between ai and ai+1. ai is between 1 and 10,000 for i=1,2,…,N, and if i≠j, then ai≠aj.

输出

Print the largest possible product of the two integers satisfying the conditions for making a pair. If any two players cannot make a pair, print -1.

样例输入

2

1 2

样例输出

2

#pragma GCC optimize(3,"Ofast","inline")
#include <stdio.h>
#include <iostream>
#include <algorithm>
#include <string.h>
#include <queue>
#include <vector>
#include <map>
#include <cmath>
#include <stack>
#include <set>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const int N = 1e3+10;
 
int a[N];
 
int main()
{
    int n;
    scanf("%d",&n);
    for(int i=1;i<=n;i++) scanf("%d",&a[i]);
    int ans=-1;
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=n;j++)
        {
            if(i==j) continue;
            int tmp=a[i]*a[j];
            vector<int>t;
            while(tmp)
            {
                t.push_back(tmp%10);
                tmp/=10;
            }
            reverse(t.begin(),t.end());
            bool flag=false;
            for(int k=0;k<t.size()-1;k++)
            {
                if(t[k+1]-t[k]!=1)
                {
                    flag=true;
                    break;
                }
            }
            if(!flag) ans=max(ans,a[i]*a[j]);
        }
    }
    printf("%d\n",ans);
    return 0;
}