头像

minux

SUFE


访客:16165

离线:13小时前


活动打卡代码 AcWing 1455. 招聘

minux
7天前
#include<cstdio>
#include<iostream>
#include<cstring>
using namespace std;

const int N=1005;
int n, m;
int a[N];

int main(){
    int T;
    cin>>T;
    while(T--){
        scanf("%d%d", &n, &m);
        for(int i=0; i<m; ++i) scanf("%d", &a[i]);

        int ans=0;
        for(int i=1, j=(n-1)%m; i<n;){
            ++i;
            j=(j+m-1)%m;
            ans=(ans+a[j])%i;
        }

        cout<<ans<<endl;
    }

    return 0;
}



minux
7天前
#include<cstring>
#include<iostream>
#include<algorithm>

using namespace std;

const int N=5005;
const int M=8192;
const int mod=1e9+7;

int n, a[N], f[2][M];
int primes[M], cnt=0;
bool vis[M];

// 线性筛找出指定范围内的质数
void Lsieve(){
    memset(primes, 0x00, sizeof primes);
    memset(vis, 0x00, sizeof vis);
    for(int i=2; i<=M; ++i){
        if(!vis[i]) primes[cnt++]=i;
        for(int j=0; primes[j]<=M/i; ++j){
            vis[primes[j]*i]=true;
            if(i%primes[j]==0) break;
        }
    }
}

int main(){
    cin>>n;
    for(int i=1; i<=n; ++i) cin>>a[i];
    Lsieve();
    memset(f, 0x00, sizeof f);
    f[0][0]=1;
    for(int i=1; i<=n; ++i)
        for(int j=0; j<M; ++j){
            f[i&1][j]=f[i-1 & 1][j];
            if((j^a[i])<M) f[i&1][j]=(f[i&1][j]+f[i-1&1][j^a[i]])%mod;
        }

    int ans=0;
    for(int i=2; i<M; ++i)
        if(!vis[i]) ans=(ans+f[n&1][i])%mod;

    cout<<ans<<endl;
    return 0;
}





活动打卡代码 AcWing 1453. 移掉K位数字

minux
9天前
#include<iostream>
using namespace std;

int main(){
    string num;
    int k;
    cin>>num>>k;
    string ans="0";
    for(int i=0; i<num.size(); ++i){
        while(k && num[i]<ans.back()){
            ans.pop_back(); 
            --k;
        }
        ans+=num[i];
    }
    while(k--) ans.pop_back(); // 如果是递增的情况,则直接弹出最后k位
    int i=0;
    while(i<ans.size() && ans[i]=='0') ++i; // 移除前导0
    if(i==ans.size()) cout<<0<<endl;
    else cout<<ans.substr(i)<<endl;

    return 0;
}


活动打卡代码 AcWing 35. 反转链表

minux
9天前
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        ListNode *pre=nullptr, *cur=head;
        while(cur){
            ListNode *post=cur->next;
            cur->next=pre;
            pre=cur;
            cur=post;
        }
        return pre;
    }
};


活动打卡代码 AcWing 1048. 鸡蛋的硬度

minux
10天前
#include<cstring>
#include<iostream>

using namespace std;

const int N=105;
const int M=15;
int f[N][M];
int n, m;

int main(){
    while(cin>>n>>m){
        for(int i=1; i<=n; ++i) f[i][1]=i; // 高度为i, 只有一个鸡蛋, 需要测量i次
        for(int i=1; i<=m; ++i) f[1][i]=1; // 高度为1, 只要测量1次即可
        for(int i=2; i<=n; ++i){
            for(int j=2; j<=m; ++j){
                f[i][j]=f[i][j-1];
                for(int k=1; k<=i; ++k)
                    f[i][j]=min(f[i][j], max(f[k-1][j-1], f[i-k][j])+1);
            }
        }
        cout<<f[n][m]<<endl;
    }
}




minux
11天前
// Forward declaration of queryAPI.
// int query(int x, int y);
// return int means matrix[x][y].

typedef long long LL;
const int INF=0x3f3f3f3f;

class Solution {
public:
    vector<int> getMinimumValue(int n) {
        int l=0, r=n-1;
        while(l<r){
            int mid=l+r>>1;
            int k;
            LL val=INF;
            for(int i=0; i<n; ++i){
                int t=query(i, mid);
                if(t<val){
                    val=t;
                    k=i;
                }
            }
            LL left=mid? query(k, mid-1):INF;
            LL right=mid+1<n?query(k, mid+1):INF;
            if(val<left && val<right) return {k, mid};
            if(left<val) r=mid-1;
            else l=mid+1;
        }
        int k;
        LL val=INF;
        for(int i=0; i<n; ++i){
            int t=query(i, r);
            if(t<val){
                val=t;
                k=i;
            }
        }
        return {k, r};
    }
};



minux
11天前
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    // 定位尾节点
    ListNode* get_tail(ListNode* head){
        while(head->next) head=head->next;
        return head;
    }

    ListNode* quickSortList(ListNode* head) {
        if(!head || !head->next) return head;
        // 定义三个子链表
        ListNode *left=new ListNode(-1); ListNode *pl=left;
        ListNode *mid=new ListNode(-1); ListNode *pm=mid;
        ListNode *right=new ListNode(-1); ListNode *pr=right;
        int val=head->val;

        // 分配元素
        for(auto p=head; p; p=p->next){
            if(p->val<val) pl=pl->next=p;
            else if(p->val==val) pm=pm->next=p;
            else pr=pr->next=p;
        }

        // 设置尾节点为nullptr
        pl->next=pm->next=pr->next=nullptr;
        // 递归左右侧
        left->next=quickSortList(left->next);
        right->next=quickSortList(right->next);

        // 拼接链表
        get_tail(left)->next=mid->next;
        get_tail(left)->next=right->next;

        // 释放空间
        auto p=left->next;
        delete left; delete mid; delete right;

        return p;
    }
};


活动打卡代码 AcWing 756. 蛇形矩阵

minux
11天前
#include<iostream>
#include<cstring>

using namespace std;

const int N=105;
int n, m, tot;
int ans[N][N];
int dirs[4][2]={{0, 1}, {1, 0}, {0, -1}, {-1, 0}};

int main(){
    memset(ans, 0x00, sizeof ans);
    cin>>n>>m;
    tot=n*m;
    for(int x=0, y=0, k=1, d=0; k<=tot; ++k){
        ans[x][y]=k;
        int nx=x+dirs[d][0];
        int ny=y+dirs[d][1];
        if(nx<0 || nx>=n || ny<0 || ny>=m || ans[nx][ny]){ // 确认新方向
            d=(d+1)%4;
            nx=x+dirs[d][0];
            ny=y+dirs[d][1];
        }
        x=nx, y=ny;
    }    

    for(int i=0; i<n; ++i){
        for(int j=0; j<m; ++j)
            cout<<ans[i][j]<<" ";
        cout<<endl;
    }

    return 0;
}



minux
12天前
#include<iostream>
#include<cstring>
#include<cmath>
#include<queue>
using namespace std;
#define ll long long
#define RG register
#define inf 1e18
#define MAX 60000
#define MAXL 500000
inline int read()
{
    RG int x=0,t=1;RG char ch=getchar();
    while((ch<'0'||ch>'9')&&ch!='-')ch=getchar();
    if(ch=='-')t=-1,ch=getchar();
    while(ch<='9'&&ch>='0')x=x*10+ch-48,ch=getchar();
    return x*t;
}
struct Line{int v,next;ll w;}e[MAXL];
int h[MAX],cnt=2;
inline void Add(int u,int v,ll w)
{
    e[cnt]=(Line){v,h[u],w};h[u]=cnt++;
    e[cnt]=(Line){u,h[v],0};h[v]=cnt++;
}
int level[MAX],cur[MAX];
bool bfs(int S,int T)
{
    memset(level,0,sizeof(level));level[S]=1;
    queue<int> Q;Q.push(S);
    while(!Q.empty())
    {
        int u=Q.front();Q.pop();
        for(int i=h[u];i;i=e[i].next)
            if(e[i].w&&!level[e[i].v])
                level[e[i].v]=level[u]+1,Q.push(e[i].v);
    }
    return level[T];
}
ll dfs(int u,int T,ll flow)
{
    if(u==T||!flow)return flow;
    ll ret=0;
    for(int &i=cur[u];i;i=e[i].next)
    {
        int v=e[i].v;ll d;
        if(e[i].w&&level[v]==level[u]+1)
        {
            d=dfs(v,T,min(flow,e[i].w));
            ret+=d;flow-=d;
            e[i].w-=d;e[i^1].w+=d;
            if(!flow)break;
        }
    }
    return ret;
}
ll Dinic(int S,int T)
{
    ll ret=0;
    while(bfs(S,T))
    {
        memcpy(cur,h,sizeof(cur));
        ret+=dfs(S,T,inf);
    }
    return ret;
}
void Fail(){puts("No Solution");}
int n,m,S,T,SS,TT,M[MAX],ans,rb;
int main()
{
    n=read();m=read();S=read();T=read();
    SS=0;TT=n+1;
    for(int i=1;i<=m;++i)
    {
        int u=read(),v=read(),B=read(),C=read();
        Add(u,v,C-B);M[u]-=B;M[v]+=B;
    }
    for(int i=1;i<=n;++i)
        if(M[i]>=0)Add(SS,i,M[i]);
        else Add(i,TT,-M[i]);
    Add(T,S,inf);rb=cnt-1;Dinic(SS,TT);
    for(int i=h[SS];i;i=e[i].next)if(e[i].w){Fail();return 0;}
    h[T]=e[h[T]].next;h[S]=e[h[S]].next;
    ans-=Dinic(T,S);ans+=e[rb].w;
    printf("%d\n",ans);
    return 0;
}



minux
12天前
#include<cstring>
#include<cstdio>
#include<queue>
#include<cmath>
using namespace std;
#define rep(i, a, b) for(int i=(a); i<=(b); ++i)
const int maxn=205;
const int maxm=10005;
const int inf=0x3f3f3f3f;
int n,m,cnt_edge=1,st,ed,S,T,sum,ans;
int head[maxn],cur[maxn],dep[maxn],in[maxn],out[maxn];
struct Edge{int u,v,down,up;}E[maxm];
struct edge{int to,nxt,flow;}e[(maxn+maxm)<<1];
inline int read() // 快读
{
    char c=getchar();int res=0,f=1;
    while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
    while(c>='0'&&c<='9')res=res*10+c-'0',c=getchar();
    return res*f;
}

inline void _add(int u,int v,int w)
{
    e[++cnt_edge].nxt=head[u];
    head[u]=cnt_edge;
    e[cnt_edge].to=v;
    e[cnt_edge].flow=w;
}
inline void add(int u,int v,int w){_add(u,v,w);_add(v,u,0);}

bool bfs()
{
    memset(dep,0,sizeof(dep));
    for(int i=0;i<=n+1;i++)cur[i]=head[i];
    queue<int>q;
    q.push(S);dep[S]=1;
    while(!q.empty())
    {
        int x=q.front();q.pop();
        for(int i=head[x];i;i=e[i].nxt)
        {
            int y=e[i].to;
            if(dep[y]||e[i].flow<=0)continue;
            dep[y]=dep[x]+1;q.push(y);
        }
    }
    return dep[T]>0;
}
int dfs(int u,int f)
{
    if(u==T||!f)return f;
    int ans=f;
    for(int i=cur[u];i;i=e[i].nxt)
    {
        cur[u]=i;
        int y=e[i].to;
        if(dep[y]!=dep[u]+1||e[i].flow<=0)continue;
        int flow=dfs(y,min(ans,e[i].flow));
        if(flow<=0)dep[y]=0;
        ans-=flow;
        e[i].flow-=flow,e[i^1].flow+=flow;
        if(ans<=0)break;
    }
    return f-ans;
}
int dinic(int x,int y)
{
    S=x,T=y;
    int ans=0;
    while(bfs()) ans+=dfs(S,inf);
    return ans;
}
int main()
{
    n=read(),m=read(),st=read(),ed=read();
    S=0,T=n+1;
    rep(i, 1, m) E[i].u=read(),E[i].v=read(),E[i].down=read(),E[i].up=read();
    rep(i, 1, m) add(E[i].u,E[i].v,E[i].up-E[i].down);
    rep(i, 1, m) in[E[i].v]+=E[i].down,out[E[i].u]+=E[i].down;
    rep(i, 1, n){
        if(in[i]>=out[i])add(S,i,in[i]-out[i]),sum+=in[i]-out[i];
        else add(i,T,out[i]-in[i]);
    }
    _add(ed,st,inf);
    if(dinic(0,n+1)!=sum){puts("No Solution");return 0;}
    ans+=e[cnt_edge^1].flow;e[cnt_edge].flow=e[cnt_edge^1].flow=0;
    for(int i=head[0];i;i=e[i].nxt)e[i].flow=e[i^1].flow=0;
    for(int i=head[n+1];i;i=e[i].nxt)e[i].flow=e[i^1].flow=0;
    ans+=dinic(st,ed);
    printf("%d\n",ans);
    return 0;
}