头像

wyf


访客:1991

离线:2小时前



wyf
7天前
#include<iostream>
#include<algorithm>
using namespace std;
const int N=1e6+10;
int q[N];
int gcd(int a,int b){//最大公约数板子
    return b?gcd(b,a%b):a;
}
int main(){
    int n,d=1e6;
    cin>>n;
    for(int i=0;i<n;i++)cin>>q[i];
    sort(q,q+n);
    bool flag=false;
    for(int i=0;i<n-2;i++){
        if(q[i]==q[i+1]){//若有两项一样那么必然是公差为0的序列
            flag=true;
            break;
        }
        d=min(d,gcd(q[i+1]-q[i],q[i+2]-q[i+1]));//d存公差,为前两项和后两项差的最大公因数
    }
    if(flag)cout<<n<<endl;
    else cout<<(q[n-1]-q[0])/d+1<<endl;
    return 0;
}



wyf
8天前
#include<iostream>
#include<cmath>
using namespace std;
int w,m,n;
int main(){
    cin>>w>>m>>n;
    int x1,x2,y1,y2;
    if(m%w==0&&(m/w)%2==0){//求偶数行第一格的情况
        x1=m/w-1;
        y1=0;
    }
    else if(m%w==0&&(m/w)%2==1){//求奇数行最后一格的情况
        x1=m/w-1;
        y1=w-1;
    }
    else if((m/w)%2==1){//求偶数行的情况
        x1=m/w;
        y1=w-m%w;
    }
    else if((m/w)%2==0){//求奇数行的情况
         x1=m/w;
        y1=m%w-1;
    }
    if(n%w==0&&(n/w)%2==0){
        x2=n/w-1;
        y2=0;
    }
    else if(n%w==0&&(n/w)%2==1){
        x2=n/w-1;
        y2=w-1;
    }
    else if((n/w)%2==1){
        x2=n/w;
        y2=w-n%w;
    }
    else {
         x2=n/w;
        y2=n%w-1;
    }
    cout<<abs(x1-x2)+abs(y1-y2)<<endl;
    return 0;
}



wyf
8天前
class Solution {
public:
    int getLastMoment(int n, vector<int>& left, vector<int>& right) {
        int res=0;
        for(int i=0;i<left.size();i++)res=max(res,left[i]);
        for(int i=0;i<right.size();i++)res=max(res,n-right[i]);
        return res;
    }
};



wyf
12天前

本题可采用快速幂的思想,一直右移,检查每一位是否为1

#include<iostream>
using namespace std;
const int N=1e6+10;
int n,cnt;
int a[N];
int main(){
    cin>>n;
    for(int i=0;i<n;i++){
        cnt=0;
        cin>>a[i];
        while(a[i]){
            if(a[i]&1)cnt++;
            a[i]>>=1;
        }
        cout<<cnt<<" ";
    }
    return 0;
}



wyf
12天前

队列做法

#include<iostream>
#include<cstring>
#include<queue>
using namespace std;
const int N=1e5+10;
int e[N],ne[N],h[N],idx;
int n,m;
int d[N];
void add(int a,int b){//用链表表示各点之间的关系
    e[idx]=b,ne[idx]=h[a],h[a]=idx++;
}
int bfs(){
    queue<int> q;
    memset(d,-1,sizeof d);
    q.push(1);
    d[1]=0;//以上两步对队列进行初始化
    while(q.size()){
        int t=q.front();
        q.pop();
        for(int i=h[t];~i;i=ne[i]){//遍历链表,更新最短距离
            int j=e[i];
            if(d[j]==-1){//只有他从未被更新才有更新的意义,因为之后再更新,必然比第一次的值大
                d[j]=d[t]+1;
                q.push(j);
            }
        }
    }
    return d[n];
}
int main(){
    memset(h,-1,sizeof h);
    cin>>n>>m;
    while(m--){
        int a,b;
        cin>>a>>b;
        add(a,b);
    }
    cout<<bfs()<<endl;
    return 0;
}


活动打卡代码 LeetCode 1518. 换酒问题

wyf
16天前
class Solution {
public:
    int numWaterBottles(int a, int b) {
        int res=a;
        while(a>=b){
            res+=a/b;
            a=a/b+a%b;
        }
        return res;
    } 
};



wyf
19天前
class Solution {
public:
    bool canMakeArithmeticProgression(vector<int>& arr) {
        if(arr.size()<=2)return true;
        sort(arr.begin(),arr.end());
        bool successful=true;
        int res=arr[1]-arr[0];
        for(int i=1,j=2;i<arr.size()&&j<arr.size();i++,j++){
            if(arr[j]-arr[i]!=res)successful=false;
        }
        if(successful)return true;
        else return false;
    }
};



wyf
20天前
class Solution {
public:
    int numIdenticalPairs(vector<int>& nums) {
        int res=0;
        for(int i=0;i<nums.size();i++){
            for(int j=i+1;j<nums.size();j++){
                if(nums[i]==nums[j])res++;
            }
        }
        return res;
    }
};


活动打卡代码 AcWing 1135. 新年好

wyf
3个月前
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <queue>

using namespace std;

typedef pair<int, int> PII;

const int N = 50010, M = 200010, INF = 0x3f3f3f3f;

int n, m;
int h[N], e[M], w[M], ne[M], idx;
int q[N], dist[6][N];
int source[6];
bool st[N];

void add(int a, int b, int c)
{
    e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx ++ ;
}

void dijkstra(int start, int dist[])
{
    memset(dist, 0x3f, N * 4);
    dist[start] = 0;
    memset(st, 0, sizeof st);

    priority_queue<PII, vector<PII>, greater<PII>> heap;
    heap.push({0, start});

    while (heap.size())
    {
        auto t = heap.top();
        heap.pop();

        int ver = t.second;
        if (st[ver]) continue;
        st[ver] = true;

        for (int i = h[ver]; ~i; i = ne[i])
        {
            int j = e[i];
            if (dist[j] > dist[ver] + w[i])
            {
                dist[j] = dist[ver] + w[i];
                heap.push({dist[j], j});
            }
        }
    }
}

int dfs(int u, int start, int distance)
{
    if (u > 5) return distance;

    int res = INF;
    for (int i = 1; i <= 5; i ++ )
        if (!st[i])
        {
            int next = source[i];
            st[i] = true;
            res = min(res, dfs(u + 1, i, distance + dist[start][next]));
            st[i] = false;
        }

    return res;
}

int main()
{
    scanf("%d%d", &n, &m);
    source[0] = 1;
    for (int i = 1; i <= 5; i ++ ) scanf("%d", &source[i]);

    memset(h, -1, sizeof h);
    while (m -- )
    {
        int a, b, c;
        scanf("%d%d%d", &a, &b, &c);
        add(a, b, c), add(b, a, c);
    }

    for (int i = 0; i < 6; i ++ ) dijkstra(source[i], dist[i]);

    memset(st, 0, sizeof st);
    printf("%d\n", dfs(1, 0, 0));

    return 0;
}


活动打卡代码 AcWing 903. 昂贵的聘礼

wyf
3个月前
#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std;

const int N = 110, INF = 0x3f3f3f3f;

int n, m;
int w[N][N], level[N];
int dist[N];
bool st[N];

int dijkstra(int down, int up)
{
    memset(dist, 0x3f, sizeof dist);
    memset(st, 0, sizeof st);

    dist[0] = 0;
    for (int i = 1; i <= n + 1; i ++ )
    {
        int t = -1;
        for (int j = 0; j <= n; j ++ )
            if (!st[j] && (t == -1 || dist[t] > dist[j]))
                 t = j;

        st[t] = true;
        for (int j = 1; j <= n; j ++ )
            if (level[j] >= down && level[j] <= up)
                dist[j] = min(dist[j], dist[t] + w[t][j]);
    }

    return dist[1];
}

int main()
{
    cin >> m >> n;

    memset(w, 0x3f, sizeof w);
    for (int i = 1; i <= n; i ++ ) w[i][i] = 0;

    for (int i = 1; i <= n; i ++ )
    {
        int price, cnt;
        cin >> price >> level[i] >> cnt;
        w[0][i] = min(price, w[0][i]);
        while (cnt -- )
        {
            int id, cost;
            cin >> id >> cost;
            w[id][i] = min(w[id][i], cost);
        }
    }

    int res = INF;
    for (int i = level[1] - m; i <= level[1]; i ++ ) res = min(res, dijkstra(i, i + m));

    cout << res << endl;

    return 0;
}