nighoc
1分钟前
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;


public class Main {
    BufferedReader in = new BufferedReader(new InputStreamReader(System.in));

    final int N = 50010, M = 500007;
    long[] h = new long[M];
    int[] id = new int[M];
    boolean[] st = new boolean[M];
    Circle[] cir = new Circle[N];
    final long NULL = Long.MIN_VALUE;

    int sqr(int x) {
        return x * x;
    }

    long get_key(int x, int y) {
        return (long)x * 1000000000 + y;
    }

    // 如果(x, y)存在, 返回它在数组中的下标, 否则返回应该插入的位置
    int find(int x, int y) {
        long key = get_key(x, y);
        int t = (int) ((key % M + M) % M);
        while(h[t] != NULL && h[t] != key) {
            t++;
            if(t == M) t = 0;
        }

        return t;
    }

    void dfs(int x, int y, int r) {
        st[find(x, y)] = true;

        for (int i = x - r; i <= x + r; i++) {
            for (int j = y - r; j <= y + r; j++) {
                if(sqr(i - x) + sqr(j - y) <= sqr(r)) {
                    int t = find(i, j);
                    if(id[t] != 0 && !st[t])
                        dfs(i, j, cir[id[t]].r);
                }
            }
        }
    }

    public Main() throws IOException {
        // 初始化哈希表
        Arrays.fill(h, NULL);

        String[] line = in.readLine().split(" ");
        int n = Integer.parseInt(line[0]);
        int m = Integer.parseInt(line[1]);

        for (int i = 1; i <= n; i++) {
            line = in.readLine().split(" ");
            int x = Integer.parseInt(line[0]);
            int y = Integer.parseInt(line[1]);
            int r = Integer.parseInt(line[2]);

            cir[i] = new Circle(x, y, r);
            int t = find(x, y);
            if(h[t] == NULL) h[t] = get_key(x, y);
            if(id[t] == 0 || r > cir[id[t]].r) {
                id[t] = i;
            }
        }

        while(m-- > 0) {
            line = in.readLine().split(" ");
            int x = Integer.parseInt(line[0]);
            int y = Integer.parseInt(line[1]);
            int r = Integer.parseInt(line[2]);

            for (int i = x - r; i <= x + r; i++) {
                for (int j = y - r; j <= y + r; j++) {
                    if(sqr(i - x) + sqr(j - y) <= sqr(r)) {
                        int t = find(i, j);
                        if(id[t] != 0 && !st[t])
                            dfs(i, j, cir[id[t]].r);
                    }


                }
            }
        }


        int res = 0;
        for (int i = 1; i <= n; i++) {
            int t = find(cir[i].x, cir[i].y);
            if(st[t]) res++;
        }
        System.out.println(res);

        in.close();
    }

    public static void main(String[] args) throws Exception {
        new Main();
    }

}

class Circle{
    int x, y, r;

    public Circle(int x, int y, int r) {
        super();
        this.x = x;
        this.y = y;
        this.r = r;
    }   
}




mozo
1分钟前

题目描述

原题链接 https://codeforces.com/contest/1622/problem/C

You are given an integer array a1,a2,…,an and integer k.

In one step you can

either choose some index i and decrease ai by one (make ai=ai−1);
or choose two indices i and j and set ai equal to aj (make ai=aj).
What is the minimum number of steps you need to make the sum of array ∑i=1nai≤k? (You are allowed to make values of array negative).

Input
The first line contains a single integer t (1≤t≤104) — the number of test cases.

The first line of each test case contains two integers n and k (1≤n≤2⋅105; 1≤k≤1015) — the size of array a and upper bound on its sum.

The second line of each test case contains n integers a1,a2,…,an (1≤ai≤109) — the array itself.

It’s guaranteed that the sum of n over all test cases doesn’t exceed 2⋅105.

Output
For each test case, print one integer — the minimum number of steps to make ∑i=1nai≤k.

样例

输入:

4
1 10
20
2 69
6 9
7 8
1 2 1 3 1 2 1
10 1
1 2 3 1 2 6 1 6 8 10

输出:

10
0
2
7

C++ 代码

#include<iostream>
#include<cstring>
#include<algorithm>
#include<vector>

typedef long long LL;

using namespace std;

const int N = 2 * 1e5 + 10;
vector<LL> a;
int t;

LL min(LL a,LL b)
{
    return  a < b ? a : b;
}

int main()
{
    cin >> t;
    while(t -- )
    {
        a.clear();
        LL n,k,sum = 0;
        cin >> n >> k;
        for(int i = 1;i <= n;i++) {
            int x;
            cin >> x;
            sum += x;
            a.push_back(x);
        }
        sort(a.begin(),a.end());
        if(k >= sum){
            cout<<"0"<<endl;
            continue;
        }
        else{
            LL res = sum - k;
            LL s = a[0] - res;
            for(int i = n - 1;i > 0;i--)
            {
                s += a[i];
                LL x;
                int y = n - i + 1;
                if(s >= 0) x = s / y;
                else x = (s- y + 1) / y;
                x = min(x,a[0]);
                res = min(res , a[0] - x + y - 1);

            }
            cout<<res<<endl;
        }
    }
    return 0;
}


新鲜事 原文

zihanwen
2分钟前
还差一人 AcWing《算法基础课》拼团优惠!https://www.acwing.com/activity/content/introduction/11/group_buy/138668/



Sleep_Madman
11分钟前

本题 要知道’A‘ 对应65 , ’a‘ 97;

字符串 最后一位 是’\0‘ , 是 Enter 上面的 那个键;

#include<bits/stdc++.h>

using namespace std ;

int main()
{
    string s ;
    cin >> s ;
    for(int i=0,len = s.length(); i<len ; i++)
    {
        if(s[i] > 64 ) {}// 65 是 A
        else
        {
            int n = s[i] - '0' ;
            for(int j=1 ;j<=n ;j++)
            {
                cout << s[i-1] ;
            }
        }

        if(s[i] > 64 && (s[i+1] >64 || s[i+1] == '\0') )
        {
            cout << s[i] ;
        }
    }

    return 0;
}


题目讨论 AcWing 94. 递归

sweetness
12分钟前

include[HTML_REMOVED]

include[HTML_REMOVED]

include[HTML_REMOVED]

using namespace std;
const int N = 10;
//全局变量初值为0
int n;
int state[N];//0表示还没放数
bool used[N];//true表示用过

void dfs(int u)
{
if(u>n)//边界
{
for(int i=1;i<=n;i++) cout<<state[i]<<” “;
cout<<endl;
return;
}

//枚举
for(int i=1;i<=n;i++)
{
    if(!used[i])
    {
        state[u]=i;
        used[i]=1;
        dfs(u+1);

        //恢复
         state[u]=0;
        used[i]=false;


    }
}

}
int main()
{
cin>>n;
dfs(1);
return 0;
}



新鲜事 原文

OCCJ
26分钟前
AcWing《第二届ACC(AcWing Cup)全国联赛》拼团优惠!https://www.acwing.com/activity/content/introduction/3043/group_buy/138702/


新鲜事 原文

OCCJ
26分钟前
AcWing《第二届ACC(AcWing Cup)全国联赛》拼团优惠!https://www.acwing.com/activity/content/introduction/3043/group_buy/138702/


新鲜事 原文

HHzp
26分钟前
AcWing《Unity3D应用课》拼团优惠!https://www.acwing.com/activity/content/introduction/2487/group_buy/138604/



题目描述

“飞行员兄弟”这个游戏,需要玩家顺利的打开一个拥有 16

个把手的冰箱。

已知每个把手可以处于以下两种状态之一:打开或关闭。

只有当所有把手都打开时,冰箱才会打开。

把手可以表示为一个 4×4
的矩阵,您可以改变任何一个位置 [i,j]

上把手的状态。

但是,这也会使得第 i
行和第 j

列上的所有把手的状态也随着改变。

请你求出打开冰箱所需的切换把手的次数最小值是多少。
输入格式

输入一共包含四行,每行包含四个把手的初始状态。

符号 + 表示把手处于闭合状态,而符号 - 表示把手处于打开状态。

至少一个手柄的初始状态是关闭的。
输出格式

第一行输出一个整数 N

,表示所需的最小切换把手次数。

接下来 N

行描述切换顺序,每行输出两个整数,代表被切换状态的把手的行号和列号,数字之间用空格隔开。

注意:如果存在多种打开冰箱的方式,则按照优先级整体从上到下,同行从左到右打开。
数据范围

1≤i,j≤4

输入样例:

-+–


-+–

输出样例:

6
1 1
1 3
1 4
4 1
4 3
4 4

样例

#include<iostream>
#include<algorithm>
#include<cstring>
#include<cstdio>
#include<vector>
//因为每一行或者每一列都可以改变对应一整行或者一整列的元素,所以一般不能用递推来操作。因为是四成四的矩阵,直接使用暴力算法进行便利

using namespace std;
//因为这里面需要记录方案,所以要开一个数组或者容器,去记录一下方案。

typedef pair <int,int> PII;
const int N =5;
char g[N][N],backup[N][N];

void turn_one(int x,int y)
{
    if(g[x][y]=='+') g[x][y]='-';
    else g[x][y]='+';
}

void turn_all(int x,int y)
{
    for(int i=0;i<4;i++)
    {   
        turn_one(x,i);
        turn_one(i,y);
    }
    turn_one(x,y);
}

int get(int x,int y)
{
    return x*4+y;
}
int main()
{
    for(int i=0;i<4;i++) cin>>g[i];
    vector<PII> res;//存储最终结果方案的一个vector容器,因为要存两个数字,所以用到了pair
    memcpy(backup,g,sizeof g);
    for(int op=0;op<(1<<16);op++)//这个1<<16表示的的是2^16,用op代表所有可能发生的情况,进行枚举。
    {   vector<PII> temp;//创建一个临时的存放结果的地方,为了更好的更新res
    //******************************************************//  
    //这段代码就是便利16位二进制数的每一位 op>>i(i是1-16) 但是这道题目是需要记录下是按了那个开关了,所以要用双重for循环+映射的形式进行操作。
        for(int i=0;i<4;i++)
        {   for(int j=0;j<4;j++)
            {
                if(op>>get(i,j)&1)//一共有16个格子,然后发现二进制位是1的就进行操作
                {
                    temp.push_back({i,j});//先把操作的内容记录下来
                    turn_all(i,j);//进行操作
                }
            }
        }    
        //**************************************************//


        //-----------------------------------------// 检查是否还有没有开着的门
        bool has_closed =false ;
        for(int i=0;i<4;i++)
            for(int j=0;j<4;j++)
                if(g[i][j]=='+') {has_closed=true;break;}
        if(!has_closed){
            if(res.empty()||res.size()>temp.size()) res=temp;//找打一个比较优的解,就要把这个目前最优的解赋给最终答案
        }
        //-------------------------------------------//
        memcpy(g,backup,sizeof g);//因为动过了g里面的内容,所以要对g中的内容进行恢复,---恢复现场
    }
    cout<<res.size()<<endl;
    for(auto p:res) cout<<p.first+1<<" "<<p.second+1<<endl;

    return 0;
}



cwr
31分钟前
#include<bits/stdc++.h>
using namespace std;
const int N=110;
const int M=25010;
int a[N];
int dp[M];//dp[N][m];
int cnt;
int main() {
    int t;
    cin>>t;
    while(t--) {
        cnt=0;
        int n;
        cin>>n;
        for(int i=1;i<=n;i++) cin>>a[i];
        sort(a+1,a+1+n);
        //初始化
        memset(dp,0,sizeof dp);//一定要重置为0
        dp[0]=1; 
        for(int i=1;i<=n;i++) {
            if(!dp[a[i]]) cnt++;
            for(int j=0;j<=a[n];j++) {
                if(j>=a[i])
                dp[j]+=dp[j-a[i]];
            }
        }
        cout<<cnt<<"\n";
    }
    return 0;
}