我他妈怎么这么菜

时间:2022-01-03 14:42:42

昨天千里万里跑回学校打那个网络赛,然并卵,没有拿到现场赛资格。
今天花了一下午一晚上时间学习树状数组,lowbit函数取x&(-x)即可得x的二进制从右往左第一个1的位置,add函数用来修改一个值以及所有包含这个元素节点的值,quiry查询是为了获得a[1]+a[2]+⋅⋅⋅⋅⋅⋅+a[x]的值,那么这个题的quiry就是找的以前的最大值加上当前的值。
YJJ's Salesman
Time Limit: 4000/2000 MS (Java/Others) Memory Limit: 65536/65536 K (Java/Others)
Total Submission(s): 1126 Accepted Submission(s): 389

 

Problem Description

YJJ is a salesman who has traveled through western country. YJJ is always on journey. Either is he at the destination, or on the way to destination.
One day, he is going to travel from city A to southeastern city B. Let us assume that A is (0,0) on the rectangle map and B (109,109). YJJ is so busy so he never turn back or go twice the same way, he will only move to east, south or southeast, which means, if YJJ is at (x,y) now (0≤x≤109,0≤y≤109), he will only forward to (x+1,y), (x,y+1) or (x+1,y+1).
On the rectangle map from (0,0) to (109,109), there are several villages scattering on the map. Villagers will do business deals with salesmen from northwestern, but not northern or western. In mathematical language, this means when there is a village k on (xk,yk) (1≤xk≤109,1≤yk≤109), only the one who was from (xk−1,yk−1) to (xk,yk) will be able to earn vk dollars.(YJJ may get different number of dollars from different village.)
YJJ has no time to plan the path, can you help him to find maximum of dollars YJJ can get.

 


Input

The first line of the input contains an integer T (1≤T≤10),which is the number of test cases.

In each case, the first line of the input contains an integer N (1≤N≤105).The following N lines, the k-th line contains 3 integers, xk,yk,vk (0≤vk≤103), which indicate that there is a village on (xk,yk) and he can get vk dollars in that village.
The positions of each village is distinct.

 


Output

The maximum of dollars YJJ can get.

 


Sample Input

1
3
1 1 1
1 2 2
3 3 1



Sample Output

3

 

#include<bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define lowbit(x) x&(-x)
const int mod = 1e9+7;
const int mx =     1e5+5;
typedef long long ll;
int x[mx];
int n;
ll sum[mx];
void add(int p,ll x){
    while(p<=n){
        sum[p] = max(sum[p],x);
        p += lowbit(p);
    }
}
ll query(int p){
    ll ans = 0;
    while(p){
        ans = max(ans,sum[p]);
        p -= lowbit(p);
    }
    return ans;
}
struct node{
    int x,y;
    ll w;
    bool operator<(const node &a)const{
        if(y != a.y) return y < a.y;
        return x > a.x;
    }
}a[mx];
int main(){
    int t;
    scanf("%d",&t);
    while(t--){
        scanf("%d",&n);
        for(int i = 1; i <= n; i++){
            scanf("%d%d%lld",&a[i].x,&a[i].y,&a[i].w);
            x[i] = a[i].x;
            sum[i] = 0;
        }
        sort(a+1,a+n+1);
        sort(x+1,x+n+1);
        ll res = 0;
        for(int i = 1; i <= n; i++){
            int k = lower_bound(x+1,x+n+1,a[i].x)-x;
            ll ans = a[i].w+query(k-1);
            add(k,ans);
            res = max(ans,res);
        }
        printf("%lld\n",res);
    }
    return 0;
}

还有一个题是pzr在做,但是他没过。。。

emmm这个题我们考虑一个新的物品跟小根堆的堆顶比较,如果新物品比堆顶还小,说明交易亏本,直接丢入堆中,否则就交易,如果堆顶的元素是已经跟之前交易过的,那么就相当于当前物品和之前那个交易,然后堆顶就变成没有交易了,继续插入堆中,交换次数不变,如果堆顶是没有交易过的,那么就交易,交易次数+2.我们希望交换次数尽可能的小,那么价值相同是,已经交换过得就有限辣

 

Buy and Resell

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/65536 K (Java/Others)
Total Submission(s): 1319    Accepted Submission(s): 434


Problem Description
The Power Cube is used as a stash of Exotic Power. There are n我他妈怎么这么菜 cities numbered 1,2,,n我他妈怎么这么菜 where allowed to trade it. The trading price of the Power Cube in the i我他妈怎么这么菜 -th city is a我他妈怎么这么菜i我他妈怎么这么菜我他妈怎么这么菜 dollars per cube. Noswal is a foxy businessman and wants to quietly make a fortune by buying and reselling Power Cubes. To avoid being discovered by the police, Noswal will go to the i我他妈怎么这么菜 -th city and choose exactly one of the following three options on the i我他妈怎么这么菜 -th day:

1. spend a我他妈怎么这么菜i我他妈怎么这么菜我他妈怎么这么菜 dollars to buy a Power Cube
2. resell a Power Cube and get a我他妈怎么这么菜i我他妈怎么这么菜我他妈怎么这么菜 dollars if he has at least one Power Cube
3. do nothing

Obviously, Noswal can own more than one Power Cubes at the same time. After going to the n我他妈怎么这么菜 cities, he will go back home and stay away from the cops. He wants to know the maximum profit he can earn. In the meanwhile, to lower the risks, he wants to minimize the times of trading (include buy and sell) to get the maximum profit. Noswal is a foxy and successful businessman so you can assume that he has infinity money at the beginning.
 

 

Input
There are multiple test cases. The first line of input contains a positive integer T我他妈怎么这么菜 (T250我他妈怎么这么菜 ), indicating the number of test cases. For each test case:
The first line has an integer n我他妈怎么这么菜 . (1n10我他妈怎么这么菜5我他妈怎么这么菜我他妈怎么这么菜 )
The second line has n我他妈怎么这么菜 integers a我他妈怎么这么菜1我他妈怎么这么菜,a我他妈怎么这么菜2我他妈怎么这么菜,,a我他妈怎么这么菜n我他妈怎么这么菜我他妈怎么这么菜 where a我他妈怎么这么菜i我他妈怎么这么菜我他妈怎么这么菜 means the trading price (buy or sell) of the Power Cube in the i我他妈怎么这么菜 -th city. (1a我他妈怎么这么菜i我他妈怎么这么菜10我他妈怎么这么菜9我他妈怎么这么菜我他妈怎么这么菜 )
It is guaranteed that the sum of all n我他妈怎么这么菜 is no more than 5×10我他妈怎么这么菜5我他妈怎么这么菜我他妈怎么这么菜 .
 

 

Output
For each case, print one line with two integers —— the maximum profit and the minimum times of trading to get the maximum profit.
 

 

Sample Input
3
4
1 2 10 9
5 9 5 9 10
5 2 2 1
 

 

Sample Output
16 4
5 2
0 0
Hint
In the first case, he will buy in 1, 2 and resell in 3, 4. profit = - 1 - 2 + 10 + 9 = 16 In the second case, he will buy in 2 and resell in 4. profit = - 5 + 10 = 5 In the third case, he will do nothing and earn nothing. profit = 0
 
#include <iostream>
#include<stdio.h>
#include<string.h>
#include<math.h>
#include<queue>
#include<algorithm>
using namespace std;
struct node
{
    int num;
    int flag;
    node()
    {

    };
    node(long long a,long long b)
    {
        num=a;
        flag=b;
    }
};
bool operator <(node a,node b)
    {
        if(a.num==b.num)
            return a.flag>b.flag;
        return a.num>b.num;
    }
int main()
{
   int t,temp,i;
   int n;
   cin>>t;
   while(t--)
   {
       long long cnt=0,sum=0;
       cin>>n;
        priority_queue<node>que;
       for(i=1;i<=n;i++)
       {
       cin>>temp;
       if(que.empty())
       {
            que.push(node(temp,1));
            continue;
       }
        node ans=que.top();
       if(temp>ans.num)
       {
           sum+=temp-ans.num;
           if(ans.flag==1)
            cnt+=2;
            que.pop();
            que.push(node(temp,0));
        }
        que.push(node(temp,1));
       }
       cout<<sum<<" "<<cnt<<endl;
       while(!que.empty())
       {
           que.pop();
       }
   }
   return 0;
}

这个题,,,一直超时最后他们跟我说根据费马小定理n>2的情况根本不存在,哭唧唧。

然后还有个什么勾股定理也可以简单判,那个定理长这样

我他妈怎么这么菜

所以说这道题其实是一道非常简单的题辣!

Find Integer

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/65536 K (Java/Others)
Total Submission(s): 1142    Accepted Submission(s): 313
Special Judge


Problem Description
people in USSS love math very much, and there is a famous math problem .

give you two integers n我他妈怎么这么菜 ,a我他妈怎么这么菜 ,you are required to find 2我他妈怎么这么菜 integers b我他妈怎么这么菜 ,c我他妈怎么这么菜 such that a我他妈怎么这么菜n我他妈怎么这么菜我他妈怎么这么菜 +b我他妈怎么这么菜n我他妈怎么这么菜=c我他妈怎么这么菜n我他妈怎么这么菜我他妈怎么这么菜 .
 

 

Input
one line contains one integer T我他妈怎么这么菜 ;(1T1000000)我他妈怎么这么菜

next T我他妈怎么这么菜 lines contains two integers n我他妈怎么这么菜 ,a我他妈怎么这么菜 ;(0n1000我他妈怎么这么菜 ,000我他妈怎么这么菜 ,000,3a40000)我他妈怎么这么菜
 

 

Output
print two integers b我他妈怎么这么菜 ,c我他妈怎么这么菜 if b我他妈怎么这么菜 ,c我他妈怎么这么菜 exits;(1b,c1000我他妈怎么这么菜 ,000我他妈怎么这么菜 ,000)我他妈怎么这么菜 ;

else print two integers -1 -1 instead.
 

 

Sample Input
1 2 3
 

 

Sample Output
4 5
 
#include <cstdio>
#include <iostream>
#include <cmath>
#include <map>
using namespace std;
int main()
{
    long long n;
    int a;
    int t;
    scanf("%d",&t);
    while(t--)
    {
        scanf("%lld %d",&n,&a);
        if(n>2) printf("-1 -1\n");
        else if(n==0) printf("-1 -1\n");
        else if(n==1) printf("1 %d\n",a+1);
        else {
            if(a==1||a==2) printf("-1 -1\n");
            else if(a%2==1){
                int sum=a*a;
                printf("%d %d\n",sum/2,sum/2+1);
            }
            else{
                int sum=a*a/2;
                printf("%d %d\n",sum/2-1,sum/2+1);
            }
        }
    }
    return 0;

}

呜呜呜,我好菜啊。