wkj

$\mathtt{O(1)}$

6551

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;
}


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;
}


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 d[1005][105];
int vis[1005][105];
int tot;
{
}
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));
{
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);
}
int qq;
scanf("%d",&qq);
for(int i=1;i<=qq;i++)
{
scanf("%d%d%d",&c,&s,&e);
bfs();
}
return 0;
}


wkj
12天前
#include<bits/stdc++.h>
using namespace std;
int T;
const int M=505;
int r,c;
char s[M][M];
int d[M*M];
int mark[M*M];
int 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){
return;
}
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=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((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]);
}
}


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;
}


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;
}


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;
}


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;
}


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;
{
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++)
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;
}


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);
}