头像

直接偷偷学习


访客:3011

离线:2小时前



/*
问题描述:
    BSNY 在学等差数列和等比数列,当已知前三项时,就可以知道是等差数列还是等比数列。
    现在给你 整数 序列的前三项,这个序列要么是等差序列,要么是等比序列,你能求出第 k 项的值吗。
    如果第 k 项的值太大,对其取模 200907。
问题求解:
    1. judge 是等差数列还是等比数列
    2. 快速幂或者是直接 k * x
*/
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <iostream>
#include <algorithm>
using namespace std;

typedef long long LL;
const int MOD = 200907;
LL a, b, c, k;

int qmi(LL a, LL b, LL MOD){
    LL res = 1;
    while(b){
        if(b & 1){
            res = res * a % MOD;
        }
        a = a * a % MOD;
        b >>= 1;
    }
    return res;
}

int main()
{
    int T;  cin>>T;
    LL res = 0;
    while(T--){
        cin>>a>>b>>c>>k;
        if(a + c == b + b){
            res = a + (k - 1) % MOD * (b - a) % MOD;
        }else{
            res = a * qmi(b / a, k - 1, MOD) % MOD;
        }
        cout<<res<<endl;
    }

    return 0;
}


活动打卡代码 AcWing 196. 质数距离

/*
问题分析与描述:
    给定两个整数L和U,你需要在闭区间[L,U]内找到距离最接近的两个相邻质数C1和C2(即C2-C1是最小的),如果存在相同距离的其他相邻质数对,则输出第一对。
    同时,你还需要找到距离最远的两个相邻质数D1和D2(即D1-D2是最大的),如果存在相同距离的其他相邻质数对,则输出第一对。
    说白了就是需要筛素数
    但是因为 1≤L<U≤2^31−1, L和U的差值不会超过1000000
问题求解:
    因为L,U太大,我们直接进行素数筛肯定是不行的,需要进行区间话的素数筛(埃氏筛可以进行区间化)
    1. 预处理出(1, U^0.5)内的素数
    2. 用筛出来的素数进行筛出 (L,U)的质数,但是这个是有一个坐标偏移量的

    而且我们一定要注意他有一个 bug 1不是质数,这个在有坐标偏移量的情况下比较容易写错
    而且你还需要注意我们的LL,因为涉及到int 的乘积判断你,转为longlong比较靠谱
*/
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;

typedef long long LL;
const int N = 1001010, M = 70010;
bool st[N];
LL prime[N], idx;
LL prime2[N], idx2;
LL l, u;

// 线性筛初始化
void Initial(int n){
    memset(st, false, sizeof st);
    idx = 0;
    for(int i = 2; i <= n; i++){
        if(!st[i]){
            prime[idx++] = i;
        }
        for(int j = 0; prime[j] <= n / i; j++){
            st[prime[j] * i] = true;
            if(i % prime[j] == 0)   break;
        }
    }
}

int main()
{
    Initial(M-10);
    //for(int i = 0; i < 15; i++) printf("%d ", prime[i]);    cout<<endl;

    while(cin>>l>>u){
        memset(st, false, sizeof st);
        for(int i = 0; i < idx; i++){   // 使用 prime[i] 筛素数
            for(LL j = max(LL(prime[i] + prime[i]), (l + prime[i] - 1) / prime[i] * prime[i]); j <= u; j += prime[i]) 
            // max(2p, (l+p-1)/p*p),j+=p
            {  
                st[j-l] = true;
            }
        }


        idx2 = 0;
        for(LL i = max(2LL, l); i <= u; i++){        // 注意,素数不可能是1,我们之前那个倍数筛法筛除不了1
            if(!st[i-l]){
                prime2[idx2++] = i;
            }
        }
        //printf("idx2 = %d\n", idx2);
        //for(int i = 0; i < idx2; i++)   printf("%d ", prime2[i]);   cout<<endl;

        if(idx2 <= 1){
            puts("There are no adjacent primes.");
        }else{
            int minv = 0, maxv = 0;
            for(int i = 1; i < idx2 - 1; i++){
                if(prime2[i+1] - prime2[i] < prime2[minv+1] - prime2[minv]){
                    minv = i;
                }
                if(prime2[i+1] - prime2[i] > prime2[maxv+1] - prime2[maxv]){
                    maxv = i;
                }
            }
            printf("%d,%d are closest, %d,%d are most distant.\n", 
                                prime2[minv], prime2[minv+1], 
                                prime2[maxv], prime2[maxv+1]);
        }
    }

    return 0;
}


活动打卡代码 AcWing 2069. 网络分析

纯并查集(按秩合并),最后一个点tle过不了,容易想到

/*
    直接使用并查集的扩展,par和son一同记录
*/
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <iostream>
using namespace std;

const int N = 10010, M = 100010;
int h[N], e[M], ne[M], idx;
int n, m;
int cnt[N];
int par[N], rk[N];
int sum;
bool st[N];         //dfs

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

// 直接初始化一手
void Initial(void){
    memset(h, -1, sizeof h);
    memset(cnt, 0, sizeof cnt);
    memset(rk, 0, sizeof rk);
    memset(st, false, sizeof st);
    idx = 0;
    for(int i = 1; i <= n + 10; i++){
        par[i] = i;
    }
}


// 直接是初始化他的par
int Find(int x){
    /*if(sum == m){
        printf("sum\n");
    }*/
    if(x == par[x]) return x;
    else return Find(par[x]);       // 注意这里不可以化简了, 我们直接是按秩合并化简复杂度
}

// a, b点进行合并
void Unite(int a, int b){
    a = Find(a), b = Find(b);
    if(rk[a] >= rk[b]){
        par[a] = b;
        add(b, a);
        cnt[a] -= cnt[b];
    }else{
        par[b] = a;
        add(a, b);
        cnt[b] -= cnt[a];
    }
}

// 并查集逆序查找
void dfs(int u){
    int v;
    for(int i = h[u]; ~i; i = ne[i]){
        v = e[i];
        st[v] = true;
        cnt[v] += cnt[u];
        dfs(v);
    }
}

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

    Initial();

    int x, a, b, p, t, fa;
    sum = 0;
    for(int i = 1; i <= m; i++){
        sum++;
        scanf("%d", &x);
        if(x == 1){
            scanf("%d%d", &a, &b);
            if(Find(a) != Find(b)){
                Unite(a, b);
            }
        }else{
            scanf("%d%d", &p, &t);
            fa = Find(p);
            cnt[fa] += t;
        }
    }
    /*
    for(int i = 1; i <= n; i++){
        printf("I:%d, Cnt:%d, par:%d\n", i, cnt[i], par[i]);
    }
    */
    for(int i = 1; i <= n; i++){
        if(par[i] == i){
            st[i] = true;
            dfs(i);
        }
    }

    for(int i = 1; i <= n; i++){
        //printf("I:%d, Cnt:%d, par:%d\n", i, cnt[i], par[i]);
        printf("%d ", cnt[i]);
    }cout<<endl;

    return 0;
}


活动打卡代码 AcWing 2067. 走方格

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <iostream>
using namespace std;

const int N = 35;
int f[N][N];
int n, m;

int main()
{
    cin>>n>>m;
    memset(f, 0, sizeof f);

    f[1][1] = 1;
    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= m; j++){
            if(i == 1 && j == 1)    continue;
            if(i % 2 == 0 && j % 2 == 0){
                f[i][j] = 0;
                continue;
            }
            if(i != 1){
                f[i][j] += f[i-1][j];
            }
            if(j != 1){
                f[i][j] += f[i][j-1];
            }
        }
    }
    /*
    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= m; j++){
            cout<<f[i][j]<<" ";
        }
        cout<<endl;
    }
    */
    cout<<f[n][m]<<endl;
    return 0;
}


活动打卡代码 AcWing 2068. 整数拼接

/*
问题分析:
    Ai + Aj * 10 ^ (leni) == 0 (mod k)
    那么我们知道 Ai, leni, 就可以知道 A[j] 对应多少个可以满足了
问题求解:
    求解思路一: Ai + Aj * 10 ^ len == 0 (mod), 直接求解同余方程,但是然后找对应的 += cnt[A[j]] 即可;
        比暴力好一些,但是复杂度可能会很高,主要是k较小时, 同余方程解太多
    求解思路二:
            Aj * 10 ^ len  使用 q[len][m]用来预处理, Ai * 10 ^ len % K == m 的个数,len最大也就是10, 复杂度不高
注意:
    一定要小心,i != j 因此cnt 的时候要判断自己是不是在里面,然后相加

这里我们采取第二种思路
*/
#include <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;

typedef long long LL;
const int N = 101010;
int a[N], len[N];
int n, k;
int q[11][N];       //预处理数组


int main()
{
    cin>>n>>k;
    int x, y;
    memset(q, 0, sizeof q);
    for(int i = 1; i <= n; i++){
        scanf("%d", &x);
        y = x;
        while(y){
            len[i]++;
            y /= 10;
        }
        // printf("I:%d, X:%d, Len:%d, Mod", i, x, len[i]);
        x = x % k;
        a[i] = x;
        for(int j = 0; j <= 10; j++){
            q[j][x%k] ++;
            x *= 10;
            x = x % k;
        }
        // cout<<a[i]<<endl;
    }

    LL res = 0;
    int target, t;
    for(int i = 1; i <= n; i++){
        target = k-a[i];
        target %= k;                //  一定要注意这个 %= k 处理
        res += q[len[i]][target];
        // printf("I:%d, a[i]:%d, q[len[i]:%d][target:%d]:%d\n", i, a[i], len[i], target, q[len[i]][target]);
        t = a[i];
        for(int j = 1; j <= len[i]; j++){
            t = t * 10 % k;
        }
        if(t == target){
            res--;
        }
    }
    cout<<res<<endl;
    return 0;
}


活动打卡代码 AcWing 2066. 解码

#include <cstring>
#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;

const int N = 1010100;
char ch[N];
int main()
{
    cin>>ch;
    int len = strlen(ch);
    for(int i = 1; i < len; i++){
        if(ch[i] >= '0' && ch[i] <= '9'){
            for(int j = 1; j <= ch[i] - '0'; j++){
                printf("%c", ch[i-1]);
            }
        }else if(!(ch[i-1] >= '1' && ch[i-1] <= '9')){
            printf("%c", ch[i-1]);
        }
    }
    if(!(ch[len-1] >= '1' && ch[len-1] <= '9')){
        cout<<ch[len-1]<<endl;
    }
    return 0;
}


活动打卡代码 AcWing 2065. 整除序列

#include <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;

typedef unsigned long long ULL;

int main()
{
    ULL n;
    cin>>n;
    while(n){
        cout<<n<<" ";
        n /= 2;
    }
    return 0;
}


活动打卡代码 AcWing 1134. 最短路计数

//这里填你的代码^^
//注意代码要放在两组三个点之间,才可以正确显示代码高亮哦~
#include<cstdio>
#include<iostream>
#include<cstring>
#include<queue>
using namespace std;
const int N=1e5+10,M=2e5+10,mod=1e5+3;
typedef pair<int,int> PII;
struct node{
    int from,to,next;
}edge[M*2];
int head[N],cnt,dis[N],num[N];
int n,m;

void addedge(int u,int v){
    cnt++;
    edge[cnt].from=u;
    edge[cnt].to=v;
    edge[cnt].next=head[u];
    head[u]=cnt;
}

void spfa(int s){
    int st[N]={0};
    dis[1]=0;
    num[s]=1;
  //  int p[N]={0};
    queue<int>q;
    q.push(s);
    st[s]=1;
    while(!q.empty()){
        int now=q.front();q.pop();
        st[now]=0;
       // p[now]++;
        for(int i=head[now];~i;i=edge[i].next){
         //   cout<<now<<" "<<edge[i].to<<" "<<dis[now]<<" "<<dis[edge[i].to]<<endl;
            if(dis[edge[i].to]<=dis[now]) continue;
            if(dis[edge[i].to]==dis[now]+1) num[edge[i].to]+=num[now];
            else num[edge[i].to]=num[now];
            num[edge[i].to]%=mod;
            dis[edge[i].to]=dis[now]+1;
            if(st[edge[i].to]) continue;
         //   if(p[edge[i].to]>N+100) continue;
            q.push(edge[i].to);
            st[edge[i].to]=1;
        }
    }
}

int main(){
    memset(head,-1,sizeof(head));
    memset(num,0,sizeof(num));
    memset(dis,0x3f,sizeof(dis));
    cin>>n>>m;
    for(int i=1,u,v;i<=m;i++){
        scanf("%d%d",&u,&v);
        addedge(u,v);
        addedge(v,u);
    }
    spfa(1);
    for(int i=1;i<=n;i++) {
        if(dis[i]==0x3f3f3f3f) cout<<0<<endl;
        else cout<<num[i]<<endl;
    }
    return 0;
}


活动打卡代码 AcWing 1131. 拯救大兵瑞恩

//这里填你的代码^^
//注意代码要放在两组三个点之间,才可以正确显示代码高亮哦~
#include<iostream>
#include<cstdio>
#include<cstring>
#include<vector>
#include<queue>
#include<cmath>
#include<deque>
const int N=13;
using namespace std;
typedef pair<int,int> PII;

int dor[2][N][N],key[N][N];//dor0表示竖着的门和墙,dor1表示横着的门和墙
int dis[int(pow(2,N))][N][N];//第1维表示是当前的状态层;(第2维,第3维)表示的是位置的坐标
int n,m,p;


int bfs(){
    int s=0;
    deque<PII>de;//创建双端队列
    int p[int(pow(2,N))][N][N]={0};
    dis[0][1][1]=0; //初始化(1,1)状态
    de.push_front(make_pair(0,1));//将当前状态放入双端队列,并且first代表当前状态,second是坐标的一维化((x-1)*m+y)
    int dx[4]={-1,0,1,0},dy[4]={0,1,0,-1};//按照上右下左的顺序进行遍历周围的四个结点
    int ix[4]={-1,0,0,0},iy[4]={0,0,0,-1};//按照上右下左的遍历边
    while(!de.empty()){
        PII now=de.front();de.pop_front();//取出队首元素,并且删除当前队首元素
        int state=now.first,x=(now.second-1)/m+1,y=now.second-(x-1)*m;//将取出的一维坐标二维化
      //  cout<<x<<" "<<y<<endl;
      //  s++;
      //  if(p[state][x][y]) continue;
      //  p[state][x][y]=1;
        if(x==n&&y==m) return dis[state][x][y];
        if(key[x][y]!=0) {
            /*if(dis[state|(1<<key[x][y])][x][y]>dis[state][x][y]){
                dis[state|(1<<key[x][y])][x][y]=dis[state][x][y];
                de.push_front(make_pair(state|(1<<key[x][y]),(x-1)*m+y));
            }*/
            if(dis[state|key[x][y]][x][y]>dis[state][x][y]) {
                dis[state|key[x][y]][x][y]=dis[state][x][y];
                de.push_front(make_pair(state|key[x][y],(x-1)*m+y));
            }
        }
        for(int i=0;i<4;i++){
            int nx=x+dx[i],ny=y+dy[i];
            if(nx<1||nx>n||ny<1||ny>m) continue;
            int inx=x+ix[i],iny=y+iy[i];
            //if(inx<1||inx>n||iny<1||iny>m) continue;
            int j=(i+1)%2;
            int w=dor[j][inx][iny];
            if(w==0) continue;
            if(w==-1||(state&(1<<w))>0) {//只有没有门或者有门并且有钥匙的时候才可以进入
                if(dis[state][nx][ny]>dis[state][x][y]+1){
                    dis[state][nx][ny]=dis[state][x][y]+1;
                    de.push_back(make_pair(state,(nx-1)*m+ny));
                }
            }
        }
    }
   // cout<<s<<endl;
    return -1;
}

int main(){
    //初始化,-1表示此处没有钥匙,没有门墙
    memset(dor,-1,sizeof(dor));
    memset(key,0,sizeof(key));
    memset(dis,0x3f,sizeof(dis));
    cin>>n>>m>>p;
    int k;cin>>k;
    for(int i=1,x1,x2,y1,y2,g,j;i<=k;i++){
        scanf("%d%d%d%d%d",&x1,&y1,&x2,&y2,&g);
        if(abs(x1-x2)==1) j=1;
        else j=0;
        dor[j][min(x1,x2)][min(y1,y2)]=g;
    }
    int s,x1,y1,g;cin>>s;
    while(s--){
        scanf("%d%d%d",&x1,&y1,&g);
        key[x1][y1]=max(key[x1][y1],key[x1][y1]|(1<<g));
    }
    int ans=bfs();
   /* int minn=0x3f3f3f3f;
    for(int i=0;i<=pow(2,p+2);i++){
        minn=min(minn,dis[i][n][m]);
    }
    if(minn==0x3f3f3f3f) cout<<"-1";
    else cout<<minn;*/
    cout<<ans;
    return 0;
}


活动打卡代码 AcWing 175. 电路维修

//这里填你的代码^^
//注意代码要放在两组三个点之间,才可以正确显示代码高亮哦~
#include<iostream>
#include<cstdio>
#include<deque>
#include<cstring>
using namespace std;
const int N=510;
typedef pair<int ,int > PII;
char gr[N][N];
int dis[N][N],r,c;

int bfs(){
    deque<PII>de;
    memset(dis,0x3f,sizeof dis);
    dis[0][0]=0;
    de.push_front(make_pair(0,0));
    int rx[4]={-1,-1,1,1},ry[4]={-1,1,1,-1};//这个是对结点进行上下左右移动的,从左上角开始顺时针的存储 
    int ix[4]={-1,-1,0,0},iy[4]={-1,0,0,-1};//这个是对当前结点按照上面方法移动之后,所需要对应的边所在的数组位置的移动方法 
    char cs[]="\\/\\/";
    while(!de.empty()){
        PII now=de.front();de.pop_front();
        for(int i=0;i<4;i++){
            int ra=now.first+rx[i],rb=now.second+ry[i];
            if(ra<0||ra>r||rb<0||rb>c) continue;
            int ia=now.first+ix[i],ib=now.second+iy[i];
            if(dis[ra][rb]>dis[now.first][now.second]+(gr[ia][ib]!=cs[i])){
                dis[ra][rb]=dis[now.first][now.second]+(gr[ia][ib]!=cs[i]);
                if(ra==r&&rb==c) return dis[ra][rb];
                if(gr[ia][ib]!=cs[i]) de.push_back(make_pair(ra,rb));
                else de.push_front(make_pair(ra,rb));
            }
        }
    }
}

int main(){
    int t;cin>>t;
    while(t--){
        cin>>r>>c;
        for(int i=0;i<r;i++)
            for(int j=0;j<c;j++)
                cin>>gr[i][j];
        if(r+c & 1) {
            cout<<"NO SOLUTION\n";
            continue;
        }
        printf("%d\n",bfs());
    }
    return 0;
}