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

提交 状态 题面

题目描述

As a participant in the BAPC (Bizarrely Awful Parties Competition) you are preparing for your next show. Now,you do not know anything about music, so you rip off someone else’s playlist and decide not to worry about that any more. What you do worry about, though, is the aesthetics of your set-up: if it looks too simple, people will be unimpressed and they might figure out that you are actually a worthless DJ.

It doesn’t take you long to come up with a correct and fast solution to this problem. You add a long strip with a couple of useless ports, and add some useless cables between these ports. Each of these cables connects two ports, and these special ports can be used more than once. Everyone looking at the massive tangle of wires will surely be in awe of your awesome DJ skills.

However, you do not want to connect the same two ports twice directly. If someone notices this, then they will immediately see that you are a fraud!

You’ve made a large strip, with the ports in certain fixed places, and you’ve found a set of cables with certain lengths that you find aesthetically pleasing. When you start trying to connect the cables, you run into another problem. If the cables are too short, you cannot use them to connect the ports! So you ask yourself the question whether you’re able to fit all of the cords onto the strip or not. If not, the aesthetics are ruined, and you’ll have to start all over again.

输入

The first line has 2 ≤ n ≤ 5 · 105 and 1 ≤ m ≤ 5 · 105, the number of ports on the strip and the number of wires.

• The second line has integers 0 ≤ x1 < · · · < xn ≤ 109, the positions of the n sockets.

• The third line has m integers l1, . . . , lm, the lengths of the wires, with 1 ≤ li ≤ 109.

输出

Print yes if it is possible to plug in all the wires, or no if this is not possible.

样例输入

4 4

0 2 3 7

1 3 3 7

样例输出

yes

#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 maxn = 1010;
const int MAXN = 1000010;
const int Hash = 13131;
const int mod =1e9+7;
ull base[MAXN],h[MAXN];
struct node
{
    int l;
    int r;
    int val;
    bool operator < (const node &x)const{
        return val>x.val;
    }
    node (int a,int b,int n){
        l=a,r=b,val=n;
    }
};
char str[MAXN];
int x[MAXN];
priority_queue<node>len;
priority_queue<int,vector<int>,greater<int> >lenans;
int main()
{
    int n,m;
    scanf("%d %d",&n,&m);
    if(m>n*(n-1)/2){
        cout<<"no"<<endl;
        return 0;
    }
    //cout<<"start"<<endl;
    for(int i=0;i<n;i++){
        scanf("%d",&x[i]);
    }
    int ttmp;
    for(int i=0;i<m;i++){
        scanf("%d",&ttmp);
        lenans.push(ttmp);
    }
    for(int i=1;i<n;i++){
        node newnode(i-1,i,x[i]-x[i-1]);
        len.push(newnode);
    }
    bool flag=true;
    while(!lenans.empty()){
        //cout<<lenans.top()<<" "<<lenans.size()<<endl;
        node tmp=len.top();
        len.pop();
 
        if(lenans.top()<tmp.val){
            flag=false;
            break;
        }
        lenans.pop();
        if(tmp.r+1<n){
            node newnode(tmp.l,(tmp.r)+1,x[tmp.r+1]-x[tmp.l]);
            len.push(newnode);
        }
 
    }
    if(flag)cout<<"yes"<<endl;
    else cout<<"no"<<endl;
    return 0;
}

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

提交 状态 题面

题目描述

Niuniu has a clock with two hands, an hour hand and a minute hand. Sometimes it looks like just having one hand because the two hands coincide. Niuniu wants to know how many times the two hands coincide from A’o clock to B’o clock (0≤A＜B≤24). (If the two hands coincide at A’o clock, it will be counted. But coincidence will not be counted at B’o clock.)

输入

Read from the standard input.

The first line contains an integer T (0 ≤ T ≤ 300) which is the number of cases.

The next T lines give two integers A and B for each case.

输出

Write to the standard output.

Output T lines, each line containing an integer as the answer of each case.

样例输入

1

14 17

样例输出

3

提示

From 14’o clock to 17’o clock, the two hands coincide three times at about 14:11,15:16 and 16:22 respectively.

#include <bits/stdc++.h>
 
using namespace std;
 
int main()
{
    int t;
    cin>>t;
    while (t--) {
        int A,B;
        scanf ("%d%d",&A,&B);
        if(A<12) {
            if(B<12) {
                printf ("%d\n",B-A);
            }
            else if(B>=12) {
                if(B==24) printf ("%d\n",B-A-2);
                else printf ("%d\n",B-A-1);
            }
        }
        else if(A>=12) {
            if(B==24) printf ("%d\n",B-A-1);
            else printf ("%d\n",B-A);
        }
    }
    return 0;
}

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

提交 状态 题面

题目描述

Alice, Bob and Yazid are good friends.

Each of them has a color, red, green or blue. Everyone’s color is different from the others’. They can describe their own colors in the format of name is color., such as Yazid is green..

Now they have made their descriptions in some order. After that, Yazid will do the following operations:

1.Connect the 3 sentences to get the initial string.

2.Remove all non-alphabetic characters.

3.Change all uppercase letters to lowercase.

For example, if the initial string is Yazid is green.Alice is red.Bob is blue., then after Yazid’s all operations, it will be turned to yazidisgreenaliceisredbobisblue.

Finally, Alice and Bob will insert any lowercase letters into any positions in this string to get the final string.

You are given the final string. Your task is to find the initial string. In particular:

•If there are multiple solutions, please output the minimum one in lexical order.

•If there is no solution, please output No solution. instead.

输入

Read from the standard input.

The first line contains one integer T (T ≤ 500), representing the number of test cases. For each case:

•One line of a string containing only lowercase letters, representing the final string.

•It is guaranteed that the length of the final string won’t exceed 600.

输出

Write to the standard output.

For each case:

•One line of a string, representing the initial string or No solution..

样例输入

4

aliceisredbobisblueyazidisgreen

aliceisgreenbobisgreenyazidisgreen

aliceisyellowbobisblueyazidisgreen

xxyazidxxisxxgreenxxbobisblueaxlxixcxexixsxrxexdx

样例输出

Alice is red.Bob is blue.Yazid is green.

No solution.

No solution.

Yazid is green.Bob is blue.Alice is red.

#pragma GCC optimize(3,"Ofast","inline")
#include <bits/stdc++.h>
 
using namespace std;
const int N=1000;
 
string s;
bool vis[30];
string outp,geti;
string name[3];
string color[3];
string out[100];
bool visn[3],visc[3];
int cnt;
 
void build(int len,string temp)
{
    if(len==3)
    {
        //cout<<temp<<endl;
        out[cnt++]=temp;
        return;
    }
    for(int i=0;i<3;i++)
    {
        if(visn[i]) continue;
        for(int j=0;j<3;j++)
        {
            if(visc[j]) continue;
            string t=temp+name[i]+" is "+color[j]+".";
            visn[i]=true;
            visc[j]=true;
            build (len+1,t);
            visn[i]= false;
            visc[j]=false;
        }
    }
}
void init()
{
    ios::sync_with_stdio (false);
    s="aliceisredbobisblueyazidisgreen";
    for(int i=0;i<s.size ();i++)  if(isalpha (s[i])) vis[s[i]-'a']= true;
    name[0]="Alice";
    name[1]="Bob";
    name[2]="Yazid";
    color[2]="red";
    color[1]="green";
    color[0]="blue";
    build(0,"");
    sort(out,out+cnt);
   // cout<<out[0]<<endl;
}
 
int main()
{
    init ();
    int T;
    cin>>T;
    while (T--)
    {
        cin>>geti;
        outp.clear();
        for(int i=0;i<geti.size();i++) if(vis[geti[i]-'a']) outp.push_back (geti[i]);
        bool flag= true;
        for(int i=0;i<cnt;i++)
        {
            int j=0;
            for(int k=0;k<outp.size ();k++)
            {
                if(outp[k]==tolower (out[i][j]))
                {
                    j++;
                    while (out[i][j]==' ' || out[i][j]=='.') j++;
                }
            }
            if(j==out[i].size ())
            {
                cout<<out[i]<<endl;
                flag=false;
                break;
            }
        }
        if(flag) cout<<"No solution."<<endl;
    }
}

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

提交 状态 题面

题目描述

John, a student who is taking the game development course, recently developed a mobile game called Fruit Slicer for his coursework. In the game the player slices fruits that are throw into the air by swiping the touch screen. However the game is quite simple because John was not able to write code for the geometry required for a more complex version. In the game each slice is a straight line of infinite length, and all fruits have the same shape of a circle with unit radius. The figure shows a cool snapshot of John’s game.

John introduces his game to his best friend Sean, who soon gets bored of playing the simple game. But as a teaching assistant of the algorithm course, Sean decides to turn the game into a homework assignment. He asks the students in the algorithms course to write a program that can compute the best slice at any given moment of the game. Given the locations of the fruits, the program should determine the maximum number of fruits that can be sliced with a single straight-line swipe.

As a student in Sean’s class, you are now the one who is facing this challenge.

输入

The first line has a single integer n (1≤n≤100). The next n lines each have two real numbers giving the x and y coordinates of a fruit. All coordinates have an absolute value no larger than 104 and are given with exactly two digits after the decimal point. Fruits may overlap.

输出

Output the maximum number of fruits that can be sliced with one straight-line swipe. A swipe slices a fruit if the line intersects the inner part or the boundary of the fruit.

样例输入

5

1.00 5.00

3.00 3.00

4.00 2.00

6.00 4.50

7.00 1.00

样例输出

4

计算几何

#include <bits/stdc++.h>
 
#define rep(i , a , b) for(int i=(a);i<=(b);i++)
using namespace std;
typedef long long ll;
 
struct Point {
    ll x , y;
 
    Point () {}
 
    Point (double _x , double _y) {
        x = _x;
        y = _y;
    }
 
    Point operator- (const Point &b) const {
        return Point (x - b.x , y - b.y);
    }
 
    ll operator^ (const Point &b) const {
        return x * b.y - y * b.x;
    }
 
    ll operator* (const Point &b) const {
        return x * b.x + y * b.y;
    }
};
 
Point operator* (Point A , ll p) {
    return Point (A.x * p , A.y * p);
}
 
struct Circle {
    Point c;
    ll r;
 
    Circle () {}
 
    Circle (Point c , ll r) : c (c) , r (r) {}
 
    bool operator< (const Circle &a) const {
        if ( a.c.x != c.x ) return c.x < a.c.x;
        return c.y < a.c.y;
    }
} e[111];
 
ll dist (Point p1 , ll a , ll b , ll c) {
    ll x = p1.x;
    ll y = p1.y;
    if ( abs (x * a + y * b + c) >= 1e9 ) return - 1;
    return ( x * a + y * b + c ) * ( x * a + y * b + c );
}
 
bool inter (ll a , ll b , ll c , Circle c1) {
    if ( dist (c1.c , a , b , c) == - 1 ) return false;
    return dist (c1.c , a , b , c) <= 1ll * 40000 * ( a * a + b * b );
}
 
bool same (Circle a , Circle b) {
    if ( a.c.x == b.c.x && a.c.y == b.c.y ) return true;
    return false;
}
 
ll read(string s) {
    ll op;
    ll ans=0;
    if(s[0]=='-') op=-1;
    else op=1;
    for(int i=0;i<s.length ();i++) {
        if(s[i]=='.'||s[i]=='-') continue;
        ans=ans*10+s[i]-'0';
    }
    return ans*op;
}
int main () {
    int n;
    scanf ("%d" , &n);
    for ( int i = 1 ; i <= n ; i ++ ) {
       string s1,s2;
       cin>>s1>>s2;
       e[ i ].c.x = read(s1);
       e[ i ].c.y = read(s2);
       e[ i ].r = 1ll * 100;
    }
    if ( n == 1 ) {
        printf ("1\n");
        return 0;
    }
    if ( n == 2 ) {
        printf ("2\n");
        return 0;
    }
    int ans = 0;
    sort (e + 1 , e + 1 + n);
    rep (i , 1 , n) {
        int res = 0;
        rep (j , 1 , n) {
            if ( same (e[ i ] , e[ j ])) res ++;
        }
        ans = max (ans , res);
    }
    int ma = 0;
    rep (i , 1 , n) {
        rep(j , i + 1 , n) {
            if ( same (e[ i ] , e[ j ])) continue;
            ll x1 = e[ i ].c.x , y1 = e[ i ].c.y;
            ll x2 = e[ j ].c.x , y2 = e[ j ].c.y;
            ll a = y2 - y1;
            ll b = x1 - x2;
            ll c = x2 * y1 - x1 * y2;
            Point v = e[ j ].c - e[ i ].c;
            int ans1 = 2;
            int ans2 = 2;
            rep (k , 1 , n) {
                if ( k == i || k == j ) continue;
                Point v1 = e[ k ].c - e[ i ].c;
                if ( inter (a , b , c , e[ k ]) && (v ^ v1) <= 0 ) ans1 ++;
                if ( inter (a , b , c , e[ k ]) && (v ^ v1) >= 0 ) ans2 ++;
            }
            ma = max (ma , max (ans1 , ans2));
        }
    }
    ans = max (ma , ans);
    cout << ans << endl;
    return 0;
}

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

提交 状态 题面

题目描述

Alice and Bob are big fans of math. In particular, they are very excited about playing games that are related to numbers. Whenever they see a puzzle like Sudoku, they cannot stop themselves from solving it. The objective of Sudoku is to fill a 9×9 grid with digits so that each column, each row, and each of the nine (3×3) subgrids that compose the grid (also called “boxes”, “blocks”, or “regions”) contains all of the digits from 1 to 9. The puzzle setter provides a partially completed grid, which for a well-posed puzzle has a single solution.

After many years of solving Sudoku problems, Alice and Bob are tired of Sudoku. They have been trying to develop a harder variation of Sudoku, which they are calling Superdoku. In Superdoku, the grid is bigger – n×n instead of just 9×9. However, the “block” constraints are impossible to formulate when there are no further constraints on n. Therefore, there are no block constraints in Superdoku. Instead, the goal is simply to make sure that each column and each row in the grid contains all of the integers from 1 to n. After playing for a while in the standard way (where any of the grid cells may have previously been filled in), they decide that the game is too difficult and they want to simplify it. Therefore, they decide to make the initial grid further constrained. They constrain the board by filling in the first k rows completely.

Alice and Bob both believe that Superdoku is solvable. However, since n could be very big, it may still take a long time to figure out a solution. They don’t want to spend too much time on this single game, so they are asking for your help!

输入

The input consists of a single test case. The first line lists two space-separated integers 1≤n≤100 and 0≤k≤n, denoting the size of the grid (n×n) and the number of rows k that are already filled in. Each of the following k lines contains n space-separated integers, denoting the first k given rows. All integers in these k lines are between 1 and n.

输出

Output either “yes” or “no” on the first line, indicating if there is a solution.

样例输入

4 2

1 2 3 4

2 3 4 1

样例输出

yes

直接验证给的k行合不合法就可以了

#pragma GCC optimize(3,"Ofast","inline")
#include<bits/stdc++.h>
 
using namespace std;
typedef  long long ll;
const int N  = 110;
typedef pair<int,int>P;
 
int n,k;
int nu[N][N];
bool visc[N][N],visr[N][N];
 
int main()
{
    bool flag=true;
    scanf("%d%d",&n,&k);
    for(int i=1;i<=k;i++)
    {
        for(int j=1;j<=n;j++)
        {
            scanf("%d",&nu[i][j]);
            if(visc[j][nu[i][j]] || visr[i][nu[i][j]]) flag=false;
            visc[j][nu[i][j]]=true;
            visr[i][nu[i][j]]=true;
        }
    }
    if(!flag)
    {
        puts("no");
        return 0;
    }
    puts("yes");
    return 0;
}

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

提交 状态 题面

题目描述

Forrest lives in a prehistoric era of “dial-up Internet.” Unlike the fast streaming of today’s broadband era, dial-up connections are only capable of transmitting small amounts of text data at reasonable speeds. Forrest has noticed that his communications typically include repeated characters, and has designed a simple compression scheme based on repeated information. Text data is encoded for transmission, possibly resulting in a much shorter data string, and decoded after transmission to reveal the original data.

The compression scheme is rather simple. When encoding a text string, repeated consecutive characters are replaced by a single instance of that character and the number of occurrences of that character (the character’s run length). Decoding the encoded string results in the original string by repeating each character the number of times encoded by the run length. Forrest calls this encoding scheme run-length encoding. (We don’t think he was actually the first person to invent it, but we haven’t mentioned that to him.)

For example, the string HHHeelllo is encoded as H3e2l3o1. Decoding H3e2l3o1 results in the original string. Forrest has hired you to write an implementation for his run-length encoding algorithm.

输入

Input consists of a single line of text. The line starts with a single letter: E for encode or D for decode. This letter is followed by a single space and then a message. The message consists of 1 to 100 characters.

Each string to encode contains only upper- and lowercase English letters, underscores, periods, and exclamation points. No consecutive sequence of characters exceeds 9 repetitions.

Each string to decode has even length. Its characters alternate between the same characters as strings to encode and a single digit between 1 and 9, indicating the run length for the preceding character.

输出

On an input of E output the run-length encoding of the provided message. On an input of D output the original string corresponding to the given run-length encoding.

样例输入

E HHHeellloWooorrrrlld!!

样例输出

H3e2l3o1W1o3r4l2d1!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;
int main()
{
    string a,b;
    cin>>a>>b;
    //cout<<a<<" "<<b<<endl;
    if(a=="E"){
        int number=0;
        char ch='\0';
        bool flag=true;
        for(int i=0;i<b.size();i++){
            if(ch==b[i]){
                number++;
            }else{
                if(!flag) printf("%d",number);
                putchar(b[i]);
                number=1;
                flag=false;
            }
            ch=b[i];
        }
        printf("%d\n",number );
    }else{
        int number=0;
        char ch = '\0';
        for(int i=0;i<b.size();i+=2){
            ch=b[i];
            number=b[i+1]-'0';
            for(int j=0;j<number;j++){
                putchar(ch);
            }
        }
        putchar('\n');
    }
    return 0;
}