g: 从N个数里找出和为N的倍数

数学题(鸽巢原理)+前缀和

处理前缀和的模N为0和相同的情况

code

void output(int i,int j){
    printf("%d\n",j-i);
    for(int t=i+1;t<=j;t++){
        printf("%d\n",a[t]);
    }
}
int main(){
    scanf("%d",&n);
        //CL(tag,-1);
        bool flag=false;//是否已经找到该组数据答案
        for(int i=1;i<=n;i++){
            scanf("%d",a+i);
            if(flag) continue;
            sum[i]=a[i];
            sum[i]+=sum[i-1];
            int mod=sum[i]%n;
            if(mod==0){
                output(0,i);
                flag=true;
                continue;
            }
            //printf("db %d %d mod %d tag[mod] %d\n",i,sum[i],mod,tag[mod]);
            if(tag[mod]==0){
                tag[mod]=i;
            }
            else{
                output(tag[mod],i);
                flag=true;
            }
        }

    
    return 0;
}

h :判断负环

bellman-ford

bellman-ford算法处理单源最短路(可以有负边),基本操作：
N-1次的松弛，每次松弛时对边 dis[v]=min(dis[v],dis[u]+cost(u,v))
不优化的复杂度O(NE)

code

struct Edge{
    int u,v,w,next;
    //Edge(int u_,int v_,int w_):u(u_),v(v_),w(w_) {}
}es[maxm];//maybe be not need u
int head[maxn];//head[u]链表头，边编号
int dis[maxn];
//init -1
int cnt;
void add(int u,int v,int w){
    es[cnt].u=u;es[cnt].v=v;es[cnt].w=w;
    es[cnt].next=head[u];
    head[u]=cnt;
    cnt++;
}
void bellman(int s){
    //原点s进行bellmanford算法
    CL(dis,0x3f);
    dis[s]=0;// dis0
    //dis1...dis(n-1)
    //dis(n)[j]=min(dis(n-1)[j],dis(n-1)[i]+cost[i][j])
    for(int t=1;t<=n-1;t++){
        //优化之一如果有一次都没更新则停止
        //便利所有边
        for(int j=0;jdis[u]+w) dis[v]=dis[u]+w;//更新
        }

    }
}
bool check(){
    //n-1次后还能更新则存在负环
    for(int j=0;jdis[u]+w) return false;
    }
    return true;
}
int main(){
    int t;
    scanf("%d",&t);
    while(t--){
        scanf("%d %d %d",&n,&m,&W);
        //初始化
        cnt=0;
        CL(head,-1);
        int u,v,w;
        
        for(int i=0;i

const int maxn=100007;
struct point{
    int x,y;
    int count;//标志有效位置
}hash[100007];
int n;
int xx[1005],yy[1005];
void tohash(int x,int y){
    int pos=(x*x+y*y+x-y)%maxn;
    while(hash[pos].count!=0){
        pos=(pos+1)%maxn;
    }
    hash[pos].count=1;
    hash[pos].x=x;hash[pos].y=y;


}
int search(int x,int y){
    int pos=(x*x+y*y+x-y)%maxn;
    while(hash[pos].count!=0){
        if(hash[pos].x==x&&hash[pos].y==y) return 1;
        pos=(pos+1)%maxn;
    }
    //printf("db search pos:%d x %d y %d\n",pos,x,y);
    //if(hash[pos].x==x&&hash[pos].y==y) return 1;
    return 0;
}

int main(){
    while(scanf("%d",&n)&&n!=0){
        CL(hash,0);
        int x,y;
        for(int i=0;i>2);

    }
    return 0;

}

struct cell{
    int x,y,z;
}cels[maxn];
int n;
bool checkadj(cell c1,cell c2){
    return (abs(c1.x-c1.x)+abs(c1.y-c2.y)+abs(c1.z-c2.z))<=1;//no same
}
int main(){
    int t;
    scanf("%d",&t);
    while(t--){
        scanf("%d",&n);
        for(int i=0;i