头像

wkj

$\mathtt{O(1)}$




离线:22小时前


活动打卡代码 AcWing 199. 余数之和

wkj
1天前
#include<bits/stdc++.h>
#define ll long long
ll ans,n,k;
using namespace std;
int main()
{
    scanf("%lld%lld",&n,&k);
    ans=n*k;
    int gx;
    for(int x=1;x<=n;x=gx+1)
    {
        if(k/x)gx=min(k/(k/x),n);
        else gx=n;
        ans-=(k/x)*(x+gx)*(gx-x+1)/2;
    }
    printf("%lld\n",ans);
    return 0;
}


活动打卡代码 AcWing 198. 反素数

wkj
1天前
#include<bits/stdc++.h>
#define ll long long
using namespace std;
ll n;
int a[11]={0,2,3,5,7,11,13,17,19,23,29};
int ans[100];
ll ans3=2000000000;
int res=0;
void dfs(int x,int i,ll num)
{
    if(x==11){
        int res2=1;
        for(int j=1;j<=10;j++)
          res2*=ans[j]+1;
        if(res2>res){
            ans3=num;
            res=res2;
        }
        else if(res2==res)ans3=min(ans3,num);
        return;
    }
    ll sum=num;
    for(int j=i;j>=0;j--){
        int ok=1;
        sum=num;
        ans[x]=j;
        for(int p=1;p<=j;p++){
            sum*=a[x];
            if(sum>n){
                ok=0;
                break;
            }
        }
        if(!ok)continue;
        dfs(x+1,j,sum);
        ans[x]=0;
    }
}
int main()
{
    scanf("%lld",&n);
    dfs(1,30,1);
    printf("%lld\n",ans3);
    return 0;
}


活动打卡代码 AcWing 176. 装满的油箱

wkj
11天前
#include<bits/stdc++.h>
using namespace std;
struct node{
    int cost,id,oil;
    bool operator<(const node &a) const{
        return a.cost<cost;
    }
};
node MKN(int x,int y,int z)
{
    node p;
    p.cost=x,p.id=y,p.oil=z;
    return p;
}
int n,m;
int p[1005];
int c,s,e;
int Next[20005],ver[20005],head[10005],edge[20005];
int d[1005][105];
int vis[1005][105];
int tot;
void add(int x,int y,int z)
{
    Next[++tot]=head[x],head[x]=tot,ver[tot]=y,edge[tot]=z;
}
priority_queue<node> q;
void bfs()
{
    while(q.size())q.pop();
    q.push(MKN(0,s,0));
    memset(d,0x3f,sizeof d);
    memset(vis,0,sizeof vis);
    d[s][0]=0;
    while(q.size())
    {
        node x=q.top();
        q.pop();
        if(x.id==e){
            printf("%d\n",x.cost);
            return;
        }
        if(vis[x.id][x.oil])continue;
        vis[x.id][x.oil]=1;
        d[x.id][x.oil]=x.cost;
        if(x.oil<c&&(d[x.id][x.oil+1]>(x.cost+p[x.id])))d[x.id][x.oil+1]=x.cost+p[x.id],q.push(MKN(x.cost+p[x.id],x.id,x.oil+1));
        for(int i=head[x.id];i;i=Next[i])
        {
            int y=ver[i],z=edge[i];
            if(x.oil>=z&&(!vis[y][x.oil-z])&&d[y][x.oil-z]>x.cost)d[y][x.oil-z]=x.cost,q.push(MKN(x.cost,y,x.oil-z));
        }
    }
    puts("impossible");
}
int main()
{
    scanf("%d%d",&n,&m);
    for(int i=0;i<n;i++)scanf("%d",&p[i]);
    for(int i=1;i<=m;i++)
    {
        int a,b,c;
        scanf("%d%d%d",&a,&b,&c);
        add(a,b,c);
        add(b,a,c);
    }
    int qq;
    scanf("%d",&qq);
    for(int i=1;i<=qq;i++)
    {
        scanf("%d%d%d",&c,&s,&e);
        bfs();
    }
    return 0;
} 


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

wkj
12天前
#include<bits/stdc++.h>
using namespace std;
int T;
const int M=505;
int r,c;
char s[M][M];
int head[M*M],Next[M*M*4],ver[M*M*4],edge[M*M*4];
int d[M*M];
int mark[M*M];
int tot;
void add(int x,int y,int z)
{
    Next[++tot]=head[x],ver[tot]=y,edge[tot]=z;
    head[x]=tot;
}
deque<int> q;
void bfs()
{
    q.clear();
    for(int i=0;i<=r*M+c;i++)mark[i]=0,d[i]=1e8;
    q.push_back(0),d[0]=0;
    while(q.size())
    {
        int x=q.front();q.pop_front();
        if(mark[x])continue;
        mark[x]=1;
        if(x==r*M+c){
            //puts("sdfhsadfhASIODFOFIPAsdfjido");
            return;
        }
        for(int i=head[x];i;i=Next[i]){
            int y=ver[i],z=edge[i];
            if(mark[y])continue;
            if(z==0){
                //printf("dfiogshdfuikasdfbfgaioseur\n");
                d[y]=min(d[y],d[x]);
                q.push_front(y);
            }
            else{
                d[y]=min(d[y],d[x]+1);
                q.push_back(y);
            }
        }
    }
}
int main()
{
    scanf("%d",&T);
    while(T--)
    {
        tot=0;
        scanf("%d%d",&r,&c);
        for(int i=0;i<=r*M+c;i++)head[i]=0;
        for(int i=1;i<=r;i++)scanf("%s",s[i]+1);
        for(int i=1;i<=r;i++)
          for(int j=1;j<=c;j++)
          {
              int a=(i-1)*M+j-1,b=(i-1)*M+j,d=i*M+j-1,e=i*M+j;
              if(s[i][j]=='/')add(a,e,1),add(e,a,1),add(b,d,0),add(d,b,0);
              else add(a,e,0),add(e,a,0),add(b,d,1),add(d,b,1);
          }
        if((r&1)!=(c&1))d[r*M+c]=1e8;
        else{
            bfs();
            //puts("hskfjasdfas");
        } 
        if(d[r*M+c]>=1e8)puts("NO SOLUTION");
        else printf("%d\n",d[r*M+c]);
    }
} 


活动打卡代码 AcWing 165. 小猫爬山

wkj
19天前
#include<bits/stdc++.h>
using namespace std;
int n,w;
int c[20];
int car[20];
int ans=1e9;
void dfs(int x,int cnt)
{
    if(cnt>=ans)return;
    if(x==n+1){
        ans=min(ans,cnt);
        return;
    }
    for(int i=1;i<=cnt;i++)
    {
        if(car[i]+c[x]<=w){
            car[i]+=c[x];
            dfs(x+1,cnt);
            car[i]-=c[x];
        }
    }
    car[cnt+1]=c[x];
    dfs(x+1,cnt+1);
    car[cnt+1]=0;
}
bool cmp(int x,int y)
{
    return x>y;
}
int main()
{
    scanf("%d%d",&n,&w);
    for(int i=1;i<=n;i++)scanf("%d",&c[i]);
    sort(c+1,c+n+1,cmp);
    dfs(1,0);
    printf("%d",ans);
    return 0;
}


活动打卡代码 AcWing 177. 噩梦

wkj
19天前
#include<bits/stdc++.h>
#define MP make_pair
using namespace std;
struct node{
    int x,y;
};
node MKN(int x,int y)
{
    node p;
    p.y=y,p.x=x;
    return p;
}
int T;
int n,m;
char s[805][805];
int tot;
int pmx,pmy,pgx,pgy,pzx[3],pzy[3];
int vis[805][805];
queue<node> man;
queue<node> girl;
int dx[]={1,-1,0,0},dy[]={0,0,1,-1};
int check(int x,int y,int k)
{
    if(x<=0||x>n||y>m||y<=0||s[x][y]=='X')return 0;
    for(int i=1;i<=2;i++)
      if(abs(x-pzx[i])+abs(y-pzy[i])<=2*k)return 0;
    return 1;
}
void bfs()
{
    while(man.size())man.pop();
    while(girl.size())girl.pop();
    man.push(MKN(pmx,pmy)),girl.push(MKN(pgx,pgy));
    vis[pmx][pmy]=1,vis[pgx][pgy]=2;
    int st=0;
    while(man.size()||girl.size())
    {
        st++;
        for(int i=1;i<=3;i++)
        {
            int len=man.size();
            for(int k=0;k<len;k++)
            {
                node p=man.front();man.pop();
                if(check(p.x,p.y,st)==0)continue;
                for(int j=0;j<4;j++)
                {
                   int x=p.x+dx[j],y=p.y+dy[j];
                   if(check(x,y,st)){
                      if(vis[x][y]==1)continue;
                      else if(vis[x][y]==2){
                        printf("%d\n",st);
                        return;
                      }
                      vis[x][y]=1;
                      man.push(MKN(x,y));
                    }
                }
            }
        }
        int len=girl.size();
        for(int i=0;i<len;i++)
        {
            node p=girl.front();girl.pop();
            if(check(p.x,p.y,st)==0)continue;
            for(int j=0;j<4;j++)
            {
               int x=p.x+dx[j],y=p.y+dy[j];
               if(check(x,y,st)){
                   if(vis[x][y]==2)continue;
                   else if(vis[x][y]==1){
                        printf("%d\n",st);
                        return;
                   }
                   vis[x][y]=2;
                   girl.push(MKN(x,y));
                }
            }
        }
    }
    printf("-1\n");
}
void solve()
{
    memset(vis,0,sizeof vis);
    tot=0;
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)scanf("%s",s[i]+1);
    for(int i=1;i<=n;i++)
      for(int j=1;j<=m;j++)
      {
         if(s[i][j]=='M')pmx=i,pmy=j;
         else if(s[i][j]=='G')pgx=i,pgy=j;
         else if(s[i][j]=='Z')pzx[++tot]=i,pzy[tot]=j;
      }
    bfs();
}
int main()
{
    scanf("%d",&T);
    while(T--)solve();
    return 0;
}


活动打卡代码 AcWing 151. 表达式计算4

wkj
20天前
#include<bits/stdc++.h>
using namespace std;
char st1[1005];
int st2[1005];
int top1=0,top2=0;
string s;
void solve()
{
    if(st1[top1]=='+')st2[top2-1]=st2[top2-1]+st2[top2];
    else if(st1[top1]=='-')st2[top2-1]=st2[top2-1]-st2[top2];
    else if(st1[top1]=='*')st2[top2-1]=st2[top2-1]*st2[top2];
    else if(st1[top1]=='/')st2[top2-1]=st2[top2-1]/st2[top2];
    else if(st1[top1]=='^')st2[top2-1]=(int)pow(st2[top2-1],st2[top2]);
    top1--,top2--;
}
int level(char c)
{ 
    if(c=='+'||c=='-') return 1;
    if(c=='*'||c=='/') return 2;
    if(c=='^') return 3;
}
int main()
{
    cin>>s;
    s='('+s+')';
    int len=s.length();
    for(int i=0;i<len;i++)
    {
        if(s[i]=='('){
            st1[++top1]=s[i];
            if(s[i+1]=='-')st2[++top2]=0;
        }
        else if(s[i]==')'){
            if(top1==0)continue;
            while(st1[top1]!='(')solve();
            top1--;
        }
        else{
            if(s[i]>='0'&&s[i]<='9')
            {
                int x=0;
                while(s[i]>='0'&&s[i]<='9')x=x*10+s[i]-'0',i++;
                i--;
                st2[++top2]=x;
            }
            else{
                if(top1==0||st1[top1]=='(')st1[++top1]=s[i];
                else if(level(s[i])<=level(st1[top1]))solve(),st1[++top1]=s[i];
                else st1[++top1]=s[i];
            }
        }
    }
    printf("%d\n",st2[1]);
    return 0;
}


活动打卡代码 AcWing 160. 匹配统计

wkj
25天前
#include<bits/stdc++.h>
#define ull unsigned long long
using namespace std;
int n,m,q;
char a[200005],b[200005];
int ans2[200005];
const int P=131;
ull p[200005],f[200005],f2[200005];
int Hash(int x1,int y1,int x2,int y2)
{
    return (f[y1]-f[x1-1]*p[y1-x1+1])==(f2[y2]-f2[x2-1]*p[y2-x2+1]);
}
int check(int x,int y)
{
    return Hash(x,x+y-1,1,y);
} 
void solve(int x)
{
    int l=1,r=m;
    int ans=0;
    while(l<=r)
    {
        int mid=(l+r)>>1;
        if(check(x,mid))ans=mid,l=mid+1;
        else r=mid-1;
    }
    ans2[ans]++;
    //printf("ans=%d,",ans);
}
int main()
{
    scanf("%d%d%d",&n,&m,&q);
    scanf("%s",a+1);
    scanf("%s",b+1);
    for(int i=1;i<=n;i++)f[i]=f[i-1]*P+a[i]-'a';
    for(int i=1;i<=m;i++)f2[i]=f2[i-1]*P+b[i]-'a';
    p[0]=1;
    for(int i=1;i<=max(n,m);i++)p[i]=p[i-1]*P;
    for(int i=1;i<=n;i++)
      solve(i);
    //puts("");
    for(int i=1;i<=q;i++)
    {
        int x;
        scanf("%d",&x);
        printf("%d\n",ans2[x]);
    }
    return 0;
}


活动打卡代码 AcWing 156. 矩阵

wkj
26天前
#include<bits/stdc++.h>
#define ull unsigned long long
using namespace std;
const int P=131,M=13331;
ull p1[1005],p2[1005];
char s[1005][1005];
ull f[1005][1005];
ull f2[1005][1005];
char c[1005][1005];
ull q[1005*1005];
int tot;
int n,m,a,b;
void ask(int x,int y)
{
    q[++tot]=f[x][y]-f[x-a][y]*p2[a]-f[x][y-b]*p1[b]+f[x-a][y-b]*p1[b]*p2[a];
}
int main()
{
    scanf("%d%d%d%d",&n,&m,&a,&b);
    for(int i=1;i<=n;i++)
      scanf("%s",s[i]+1);
    for(int i=1;i<=n;i++)
      for(int j=1;j<=m;j++)
        f[i][j]=f[i][j-1]*P+s[i][j]-'0';
    for(int i=1;i<=n;i++)
      for(int j=1;j<=m;j++)
        f[i][j]+=f[i-1][j]*M;
    p2[0]=1;
    p1[0]=1;
    for(int i=1;i<=1004;i++)p1[i]=p1[i-1]*P;
    for(int i=1;i<=1004;i++)p2[i]=p2[i-1]*M;
    for(int i=a;i<=n;i++)
      for(int j=b;j<=m;j++)
        ask(i,j);
    sort(q+1,q+tot+1);
    int Q;
    scanf("%d",&Q);
    for(int i=1;i<=Q;i++)
    {
        memset(f2,0,sizeof(f2));
        for(int d=1;d<=a;d++)
          scanf("%s",c[d]+1);
        for(int d=1;d<=a;d++)
          for(int j=1;j<=b;j++)
            f2[d][j]=f2[d][j-1]*P+c[d][j]-'0';
        for(int d=1;d<=a;d++)
          for(int j=1;j<=b;j++)
            f2[d][j]+=f2[d-1][j]*M;
        int pos=lower_bound(q+1,q+tot+1,f2[a][b])-q;
        //printf("%llu\n",f2[a][b]);
        //printf("%d\n",pos);
        if(q[pos]==f2[a][b])puts("1");
        else puts("0");
    }
    return 0;
} 


活动打卡代码 AcWing 149. 荷马史诗

wkj
26天前
#include<bits/stdc++.h>
#define ll long long
#define PA pair<ll,ll>
using namespace std;
int n,k;
ll a[100005];
priority_queue<PA,vector<PA>,greater<PA> > q;
ll ans;
int main()
{
    scanf("%d%d",&n,&k);
    for(int i=1;i<=n;i++)scanf("%lld",&a[i]),q.push(make_pair(a[i],1));
    while((q.size()-1)%(k-1))q.push(make_pair(0,1));
    while(q.size()!=1)
    {
        ll deep=1;
        ll tot=0;
        for(int i=1;i<=k;i++)tot+=q.top().first,deep=max(deep,q.top().second),q.pop();
        q.push(make_pair(tot,deep+1));
        ans+=tot;
    }
    printf("%lld\n%lld",ans,q.top().second-1);
}