Koan_
1小时前

一开始还以为要离散化,后来发现就只是单调队列的题目

一般的单调队列对于每个位置来说只有一个点,这道题目区别在于一个位置可能有很多个气球

那么就开一个结构体记录 节点信息为(位置+气球种类编号) 然后对位置做排序

最后跑一遍单调队列就可以了!

/*
 *2021/12/6
 */
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
#include<unordered_map>

using namespace std;

typedef pair<int,int> pii;
typedef long long ll;

const int N=1e6+10;

int n,k;
struct Node{
    int ver,place;
    bool operator <(const Node &t) const{
        return place<t.place;
    }
}p[N];
int cnt;

unordered_map<int,int> mp;
int cnt_mp;

int main()
{
    cin>>n>>k;
    for(int i=1;i<=k;i++){
        int t;
        scanf("%d",&t);
        for(int j=1;j<=t;j++){
            int place;
            scanf("%d",&place);
            p[++cnt]={i,place};
        }
    }
    sort(p+1,p+1+cnt);
    /*for(int i=1;i<=cnt;i++){
        printf("place is: %d ver is %d\n",p[i].place,p[i].ver);
    }*/
    int ans=0x3f3f3f3f;
    int l=1;
    for(int r=1;r<=cnt;r++){
        if(!mp.count(p[r].ver)) cnt_mp++;
        mp[p[r].ver]++;
        while(mp[p[l].ver]>1){
            mp[p[l].ver]--;
            l++;
        }
        if(cnt_mp==k){
            /*printf("now case is: ");
            printf("left is %d right is %d\n",p[l].place,p[r].place);*/
            ans=min(ans,p[r].place-p[l].place);
        }
    }
    cout<<ans<<endl;
    return 0;
}



brivia
3小时前

9 * 10 算得出来吗?




sssk
3小时前

二维(城市,剩下油)状态的bfs

#include<bits/stdc++.h>
using namespace std;
typedef pair<int, int> pii;
const int N = 1010, M = 20010, H = 110;
int oil_price[N];
int e[M], ne[M], w[M], h[N], idx;
int d[N][H], ans;//d[i][j],表示到达城市i,剩下油为j的最小花费
int n, m, question, C, s, en;
struct P{//结构体
    int city, fuel, cost;//分别表示当前城市,油,花费
};
auto cmp = [](const P& A, const P& B) {return A.cost > B.cost;};
priority_queue<P, vector<P>, decltype(cmp)> pq(cmp);//按照花费排序的结构体
//添加一条由a到b的边, 边权为k2
void add(int a, int b, int k){
    w[idx] = k;
    e[idx] = b;
    ne[idx] = h[a];
    h[a] = idx++;
}
void init(){//初始化
    memset(d, -1, sizeof d);
    ans = 0;
    while(!pq.empty()) pq.pop();
}
int main(){
    memset(h, -1, sizeof h);
    cin >> n >> m;
    for(int i = 0; i < n; i++) cin >> oil_price[i];
    for(int i = 1; i <= m; i++){
        int a, b, k;
        cin >> a >> b >> k;
        add(a,b,k);
        add(b,a,k);
    }
    cin >> question;
    while(question--){
        init();
        cin >> C >> s >> en;
        pq.push({s,0,0});
        while(pq.size()){
            auto now = pq.top(); pq.pop();
            int ci = now.city, f = now.fuel, co = now.cost;
            d[ci][f] = co;
            if(ci == en)//一旦遇到终点城市就输出,不然TLE
            {
                cout << co << endl;
                break;
            }
            if(f < C) pq.push({ci, f + 1, co + oil_price[ci]});
            for(int i = h[ci]; ~i; i = ne[i]){
                if(f >= w[i] && d[e[i]][f-w[i]] == -1)
                    pq.push({e[i], f - w[i], co});
            }
        }
        if(d[en][0] == -1) cout << "impossible\n";
    }
    return 0;
}



风之羁绊
4小时前

题目描述

假设你是一个专业的狗仔,参加了一个 n 人派对,其中每个人被从 0 到 n - 1 标号。在这个派对人群当中可能存在一位 “名人”。所谓 “名人” 的定义是:其他所有 n - 1 个人都认识他/她,而他/她并不认识其他任何人。

现在你想要确认这个 “名人” 是谁,或者确定这里没有 “名人”。而你唯一能做的就是问诸如 “A 你好呀,请问你认不认识 B呀?” 的问题,以确定 A 是否认识 B。你需要在(渐近意义上)尽可能少的问题内来确定这位 “名人” 是谁(或者确定这里没有 “名人”)。

在本题中,你可以使用辅助函数 bool knows(a, b) 获取到 A 是否认识 B。请你来实现一个函数 int findCelebrity(n)。

派对最多只会有一个 “名人” 参加。若 “名人” 存在,请返回他/她的编号;若 “名人” 不存在,请返回 -1。

样例

输入: graph = [
  [1,1,0],
  [0,1,0],
  [1,1,1]
]
输出: 1
解释: 有编号分别为 0、1 和 2 的三个人。graph[i][j] = 1 代表编号为 i 的人认识编号为 j 的人,而 graph[i][j] = 0 则代表编号为 i 的人不认识编号为 j 的人。“名人” 是编号 1 的人,因为 0 和 2 均认识他/她,但 1 不认识任何人。


算法1

(暴力枚举) $O(n)$

每次比较,都能淘汰一个,所以通过n-1次比较能确定一个可能的答案,再需要通过2个(n-1)次进行校验这个答案

时间复杂度

参考文献

C++ 代码

/* The knows API is defined for you.
      bool knows(int a, int b); */

class Solution {
public:
    int findCelebrity(int n) {
        int result = 0;
        for(int i=1;i<n;i++){
            if(knows(result,i))
                result = i;
        }

        for(int i=0;i<n;i++){
            if(result==i) continue;
            if(knows(result,i)||knows(i,result)==0) return -1;
        }
        return result;
    }
};




可达
4小时前

include[HTML_REMOVED]

int main()
{
int n;
scanf(“%d”,&n);
while(n–)
{
int a;
int b=0;
scanf(“%d”,&a);
for(int i=2;i*i<=a;i++)
{
if(a%i==0)
{
b=1;
}
}
if(b==0)
printf(“%d is prime\n”,a);
if(b==1)
printf(“%d is not prime\n”,a);
}
return 0;
}




dark_7
4小时前
#define _CRT_SECURE_NO_WARNINGS
#include <bits/stdc++.h>
#include <iostream>
#include <algorithm>
#include <cmath>
#include <cstring>
#include <cstdio>
#include <iomanip>
#include <sstream>
#include <vector>
//#include <list>
//#include <stack>
//#include <queue>
//#include <set>
//#include <map>

#define endl "\n"
using namespace std;

typedef long long LL;
typedef unsigned long long uLL;

int n;
int a[10];
int f[10];

void dfs(int u) {
    if (u > n) {
        for (int i = 1;i <= n;i++)
            cout << a[i] << ' ';
        cout << endl;
    }

    for (int i = 1;i <= n;i++) {
        if (f[i] == 0)
        {
            a[u] = i;
            f[i] = 1;
            dfs(u + 1);
            f[i] = 0;
        }
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);

    cin >> n;
    dfs(1);

    return 0;
}



/*
IDA*这个算法的思想其实比A*要好理解很多
简单来说就是我们开一个估计函数这个估计函数的返回值一定比真实值要小这样我们就可以利用这个进行最优化减枝
如果估计函数都无法完成那么真实值一定也无法完成可以直接剪掉
这题由于步数很小答案可能会很大所以我们再用一下之前讲的迭代加深的思想来优化一下搜索
这题我们搜索可以去枚举我们选择的长度以及我们放的位置去搜索
这题我们其实可以不用往前放因为我们往前放会对应前面的一种选法完全没有必要
这题由于每次我们最多改变3个位置的关系所以假设我们有k个错误前后关系那么(k+2)/3就是我们最多要操作的次数
可以看到估计函数的影子了所以我们这题再用IDA*来优化
我们可以用这个(k+2)/3来当成估计函数
*/
#include <iostream>
#include <cstring>
#include <algorithm>
#include<stdio.h>
using namespace std;
const int N = 30;
int di[10][N];
int qi[N];
int n;
int f()
{
    int cnt=0;
    for(int i=1;i<=n-1;i++)
    {
        if(qi[i]+1!=qi[i+1])cnt++;
    }
    return (cnt+2)/3;
}
bool check()
{
    for(int i=1;i<=n-1;i++)
    {
        if(qi[i]+1!=qi[i+1])return false;
    }
    return true;
}
bool dfs(int u,int depth)
{
    if(u+f()>depth)return false;
    if(check())return true;
    for(int len=1;len<=n;len++)
    {
        for(int i=1;i+len-1<=n;i++)
        {
            int j=i+len-1;
            for(int k=j+1;k<=n;k++)
            {
                int y=i;
                memcpy(di[u+1],qi,sizeof qi);
                for(int d=j+1;d<=k;d++,y++)
                {
                    qi[y]=di[u+1][d];
                }
                for(int d=i;d<=j;d++,y++)
                {
                    qi[y]=di[u+1][d];
                }
                if(dfs(u+1,depth))return true;
                memcpy(qi,di[u+1],sizeof qi);
            }
        }
    }
    return false;
}
int main()
{
    int t;
    cin >> t;
    while(t--)
    {

        cin >> n;
        for(int i=1;i<=n;i++)
        {
            cin >> qi[i];
        }
        int depth=0;
        while(depth<5&&!dfs(0,depth))depth++;
        if(depth>=5) cout << "5 or more"<<endl;
        else cout << depth<<endl;
    }
    return 0;
}



风之羁绊
4小时前

题目描述

请在 n × n 的棋盘上,实现一个判定井字棋(Tic-Tac-Toe)胜负的神器,判断每一次玩家落子后,是否有胜出的玩家。

在这个井字棋游戏中,会有 2 名玩家,他们将轮流在棋盘上放置自己的棋子。

在实现这个判定器的过程中,你可以假设以下这些规则一定成立:

1. 每一步棋都是在棋盘内的,并且只能被放置在一个空的格子里;

2. 一旦游戏中有一名玩家胜出的话,游戏将不能再继续;

3. 一个玩家如果在同一行、同一列或者同一斜对角线上都放置了自己的棋子,那么他便获得胜利。

样例

给定棋盘边长 n = 3, 玩家 1 的棋子符号是 "X",玩家 2 的棋子符号是 "O"。

TicTacToe toe = new TicTacToe(3);

toe.move(0, 0, 1); -> 函数返回 0 (此时,暂时没有玩家赢得这场对决)
|X| | |
| | | |    // 玩家 1 在 (0, 0) 落子。
| | | |

toe.move(0, 2, 2); -> 函数返回 0 (暂时没有玩家赢得本场比赛)
|X| |O|
| | | |    // 玩家 2 在 (0, 2) 落子。
| | | |

toe.move(2, 2, 1); -> 函数返回 0 (暂时没有玩家赢得比赛)
|X| |O|
| | | |    // 玩家 1 在 (2, 2) 落子。
| | |X|

toe.move(1, 1, 2); -> 函数返回 0 (暂没有玩家赢得比赛)
|X| |O|
| |O| |    // 玩家 2 在 (1, 1) 落子。
| | |X|

toe.move(2, 0, 1); -> 函数返回 0 (暂无玩家赢得比赛)
|X| |O|
| |O| |    // 玩家 1 在 (2, 0) 落子。
|X| |X|

toe.move(1, 0, 2); -> 函数返回 0 (没有玩家赢得比赛)
|X| |O|
|O|O| |    // 玩家 2 在 (1, 0) 落子.
|X| |X|

toe.move(2, 1, 1); -> 函数返回 1 (此时,玩家 1 赢得了该场比赛)
|X| |O|
|O|O| |    // 玩家 1 在 (2, 1) 落子。
|X|X|X|


算法1

(暴力枚举) $O(n)$

枚举每个选手在每行,每列,两条对角线上的数量,数量为n时,则获胜。

时间复杂度

C++ 代码

class TicTacToe {
public:
    vector<vector<int>> r,c;
    vector<int> d1,d2;
    int n;
    TicTacToe(int n) {
        this->n = n;
        r = c = vector<vector<int>>(2,vector<int>(n));
        d1 = d2 = vector<int>(2);
    }

    int move(int row, int col, int player) {
        r[player-1][row]++;
        c[player-1][col]++;
        if(r[player-1][row]==n || c[player-1][col]==n) return player;
        if(row==col) {
            d1[player-1]++;
            if(d1[player-1]==n)
                return player;
        }
        if(row+col==n-1){
            d2[player-1]++;
            if(d2[player-1]==n)
                return player;
        }
        return 0;
    }
};




qgc123
4小时前
#include<iostream>
#include<unordered_map>
#include<cstring>
#include<vector>
using namespace std;
unordered_map<int, vector<int>> mp;
const int N = 200005;
int st[N];
int res[N];
int func(int u)
{
    st[u] = 1;
    for(auto i : mp [u])
    {
        if (!st[i])
        {
            st[i] = 1;
            if (res[i] == 0 || func(res[i]))
            {
                res[i] = u;
                return 1;
            }
        }
    }
    return 0;
}


int main()
{ 
    int n1, n2, m;
    cin >> n1 >> n2 >> m;
    for (int i = 0; i < m; i++)
    {
        int a, b;
        cin >> a >> b;
        mp[a].push_back(b);
    }
    int ans = 0;
    for (int i = 1; i <= n1; i++)
    {
        memset(st, 0, sizeof st);
            ans+=func(i);
    }
    cout << ans;
}



qgc123
4小时前
#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
const int N = 510, M = 10010;
int n,m,k;
struct ed
{
    int a, b, c;
}edge[M];
int d[N], la[N];

void bellman_ford(){
    memset(d, 0x3f, sizeof d);
    d[1] = 0;
    for (int i = 0; i < k;i++){
        memcpy(la, d, sizeof(d));
        for (int j = 0; j < m;j++){
            auto e= edge[j];
            d[e.b] = min(d[e.b], la[e.a] + e.c);
        }
    }
}
int main(){
    cin >> n >> m >> k;
    for(int i=0;i<m;i++){
        int a, b, c;
        cin >> a >> b >> c;

        edge[i] = {a, b, c};
    }
    bellman_ford();
    if(d[n]>0x3f3f3f3f/2)
        cout << "impossible" << endl;
        else{
            cout << d[n] << endl;
        }
        return 0;
}