A - 超级赛亚ACMer
n m k
m >=max( a[i] );
m < min(a[i]); 先判断掉 然后就可以找到最接近的 比m小的一个数 往上涨 看是否能行 O(n)
#include<stdio.h>
#include<string.h>
#include<algorithm>
#include<string>
#include<iostream>
#include<math.h>
using namespace std;
#define MAXN 10010
#define ll long long
#define exp 1e-8
ll z[MAXN];
bool cmp(ll a,ll b)
{
return a>b;
}
int main()
{
int t;
scanf("%d",&t);
int ca=1;
while(t--)
{
int n,m,k;
scanf("%d%d%d",&n,&m,&k);
for(int i=1;i<=n;i++)
scanf("%lld",&z[i]);
printf("Case #%d:\n",ca++);
sort(z+1,z+n+1,cmp);
if(m>=z[1])
printf("why am I so diao?\n");
else if(z[n]>m)
printf("madan!\n");
else
{
int ind;
for(int i=n;i>=1;i--)
{
if(z[i]>m)
{
ind=i+1;
break;
}
}
int ok=0;
ll a=k;
ll now=z[ind];
for(int i=ind;i>=2;i--)
{
if(now+a>=z[1])
{
ok=1;
break;
}
if(now+a<z[i-1])
break;
now=z[i-1];
if(a>=1)
a--;
}
if(ok==1)
printf("why am I so diao?\n");
else
printf("madan!\n");
}
}
return 0;
}
B - 找连续数
n*n预处理 O（1）查询 放到set里判断有没有相同 准确的是n*n*log(n)
#include<stdio.h>
#include<string.h>
#include<algorithm>
#include<string>
#include<iostream>
#include<math.h>
#include<map>
using namespace std;
#define MAXN 100010
#define ll long long
#define exp 1e-8
ll z[10001];
int ans[1010];
map<ll,int>m1;
int main()
{
int n,m;
int ca=1;
while(scanf("%d%d",&n,&m)!=EOF)
{
for(int i=1;i<=n;i++)
scanf("%lld",&z[i]);
memset(ans,0,sizeof(ans));
for(int i=1;i<=n;i++)
{
int mi=z[i];
int mx=z[i];
m1.clear();
for(int j=i;j<=n;j++) //j-i+1
{
m1[z[j]]++;
if(m1[z[j]]>1)
break;
if(z[j]>mx)
mx=z[j];
if(z[j]<mi)
mi=z[j];
if(mx-mi+1==j-i+1)
ans[j-i+1]++;
}
}
printf("Case #%d:\n",ca++);
while(m--)
{
int a;
scanf("%d",&a);
printf("%d\n",ans[a]);
}
}
return 0;
}
C - 序列变换
很自然的想法 什么都想不到 那么二分答案 log(n) 很优秀的复杂度 然后n的贪心 O(n*log(n))
#include<stdio.h>
#include<string.h>
#include<algorithm>
#include<string>
#include<iostream>
#include<math.h>
using namespace std;
#define MAXN 100010
#define ll long long
#define exp 1e-8
int z[MAXN];
int x[MAXN];
int n;
bool jud(int a)
{
x[1]=z[1]-a;
for(int i=2;i<=n;i++)
{
if(z[i]+a<=x[i-1])
return 0;
x[i]=max(x[i-1]+1,z[i]-a);
}
return 1;
}
int main()
{
int t;
scanf("%d",&t);
int ca=1;
while(t--)
{
scanf("%d",&n);
for(int i=1;i<=n;i++)
scanf("%d",&z[i]);
int l=0;
int r=10000000;
int ans=r;
while(l<=r)
{
int mid=(l+r)>>1;
if(jud(mid))
{
ans=mid;
r=mid-1;
}
else
l=mid+1;
}
printf("Case #%d:\n",ca++);
printf("%d\n",ans);
}
return 0;
}
D - KPI
这种求中间的那个往往要用2个数据结构来维护 2个set 前面多了往后面 后面多了往前面 删除的话 在2和set里面都找一下 然后丢出第一个set里面最大的 O(nlog(n))
#include<stdio.h>
#include<string.h>
#include<algorithm>
#include<string>
#include<iostream>
#include<math.h>
#include<map>
#include<set>
#include<queue>
using namespace std;
#define MAXN 100010
#define ll long long
#define exp 1e-8
queue<int>q1;
set<int>s1,s2;
int main()
{
int n;
int ca=1;
while(scanf("%d",&n)!=EOF)
{
s1.clear();
s2.clear();
while(!q1.empty())
q1.pop();
printf("Case #%d:\n",ca++);
int num=0;
while(n--)
{
char s[10];
scanf("%s",s);
if(s[0]=='q')
{
set<int>::iterator i=s1.end();
i--;
printf("%d\n",*i);
}
else if(s[0]=='o')
{
int a=q1.front();
q1.pop();
set<int>::iterator i=s1.find(a);
if(i==s1.end())
{
i=s2.find(a);
s2.erase(i);
if(s1.size()-s2.size()>2)
{
set<int>::iterator j=s1.end();
j--;
int b=*j;
s2.insert(b);
s1.erase(j);
}
}
else
{
s1.erase(i);
if(s1.size()==s2.size())
{
if(s2.size()>=1)
{
set<int>::iterator j=s2.begin();
int b=*j;
s1.insert(b);
s2.erase(j);
}
}
}
num--;
}
else
{
int c;
scanf("%d",&c);
q1.push(c);
int a=s1.size();
if(a==0)
{
s1.insert(c);
}
else
{
set<int>::iterator i=s1.end();
i--;
if(c>*i)
{
s2.insert(c);
if(s1.size()-s2.size()==0)
{
set<int>::iterator j=s2.begin();
int a=*j;
s1.insert(a);
s2.erase(j);
}
}
else
{
s1.insert(c);
if(s1.size()-s2.size()>2)
{
set<int>::iterator j=s1.end();
j--;
int a=*j;
s2.insert(a);
s1.erase(j);
}
}
}
num++;
}
}
}
return 0;
}
B - 连接的管道
不错的最小生成树 O(nlog(n))
C - 棋盘占领
一直跑 直到没的增加
E - 序列变换
a[i]<a[j]
a[i]-i<=a[j]-j
变换之后 求非严格lis O(nlog(n))
n - len;
#include<stdio.h>
#include<string.h>
#include<algorithm>
#include<string>
#include<iostream>
#include<math.h>
#include<map>
#include<set>
#include<queue>
using namespace std;
#define MAXN 100010
#define ll long long
#define exp 1e-8
#define inf 1000000007
int z[MAXN];
int dp[MAXN];
int main()
{
int t;
scanf("%d",&t);
int ca=1;
while(t--)
{
int n;
scanf("%d",&n);
for(int i=1;i<=n;i++)
{
scanf("%d",&z[i]);
z[i]=z[i]-i;
}
printf("Case #%d:\n",ca++);
dp[0]=-inf;
int cnt=0;
for(int i=1;i<=n;i++)
{
if(z[i]>=dp[cnt])
{
dp[++cnt]=z[i];
}
else
{
int x=upper_bound(dp,dp+cnt,z[i])-dp;
dp[x]=z[i];
}
}
printf("%d\n",n-cnt);
}
return 0;
}
F - Friendship of Frog
n*n
K - Kingdom of Black and White
t组样例
01串 最多可以改变一个 每个连续的0或者1分在一起 要求的是 连续的长度 的平方的和 最大
我用的维护前后缀 到达i 求得不改字母到i的贡献
然后枚举每个位子 二分结束的位子 求贡献 就行 O(nlog(n))
#include<stdio.h>
#include<string.h>
#include<algorithm>
#include<string>
#include<iostream>
#include<math.h>
#include<map>
#include<set>
#include<queue>
using namespace std;
#define MAXN 100010
#define ll long long
#define exp 1e-8
#define inf 1000000007
char z[MAXN];
ll pre[MAXN],le[MAXN];
int x[MAXN],y[MAXN];
int main()
{
int t;
scanf("%d",&t);
int ca=1;
while(t--)
{
scanf("%s",z+1);
int len=strlen(z+1);
printf("Case #%d: ",ca++);
pre[0]=0;
int cnt=1;
int ind=0;
for(int i=2;i<=len;i++)
{
if(z[i]!=z[i-1])
{
pre[i-1]=pre[ind]+(ll)cnt*cnt;
cnt=1;
ind=i-1;
}
else
{
pre[i-1]=pre[ind]+(ll)cnt*cnt;
cnt++;
}
}
pre[len]=pre[ind]+(ll)cnt*cnt;
le[len+1]=0;
cnt=1;
ind=len+1;
for(int i=len-1;i>=1;i--)
{
if(z[i]!=z[i+1])
{
le[i+1]=le[ind]+(ll)cnt*cnt;
cnt=1;
ind=i+1;
}
else
{
le[i+1]=le[ind]+(ll)cnt*cnt;
cnt++;
}
}
le[1]=le[ind]+(ll)cnt*cnt;
x[0]=y[0]=0;
for(int i=1;i<=len;i++)
{
if(z[i]=='0')
{
x[i]=x[i-1]+1;
y[i]=y[i-1];
}
else
{
x[i]=x[i-1];
y[i]=y[i-1]+1;
}
}
ll mx=0;
for(int i=1;i<=len;i++)
{
if(z[i]=='0')
{
int l=i;
int r=len;
int ans=i;
while(l<=r)
{
int mid=(l+r)>>1;
if(y[mid]-y[i-1]<=1)
{
l=mid+1;
ans=mid;
}
else
r=mid-1;
}
mx=max(mx,pre[i-1]+le[ans+1]+(ll)(ans-i+1)*(ans-i+1));
}
else
{
int l=i;
int r=len;
int ans=i;
while(l<=r)
{
int mid=(l+r)>>1;
if(x[mid]-x[i-1]<=1)
{
l=mid+1;
ans=mid;
}
else
r=mid-1;
}
mx=max(mx,pre[i-1]+le[ans+1]+(ll)(ans-i+1)*(ans-i+1));
}
}
printf("%lld\n",mx);
}
return 0;
}
L - LCM Walk
t组样例
sx sy 可以走到 sx sy+lcm(sx,sy) 或者 sx+lcm(sx,sy),sy
现在给出 终点ex,ey 求有多少点可以走到这里
不妨写成这样 pt ,qt lcm=pqt
那么就是 pt+pqt,qt ex ey -> ex/(1+ey),ey
还有一点就是 x < y 那么 肯定是 x y变了 过来的
#include<stdio.h>
#include<string.h>
#include<algorithm>
#include<string>
#include<iostream>
#include<math.h>
#include<map>
#include<set>
#include<queue>
using namespace std;
#define MAXN 100010
#define ll long long
#define exp 1e-8
#define inf 1000000007
ll gcd(ll a,ll b)
{
return b?gcd(b,a%b):a;
}
int ans;
void solve(int x,int y)
{
ans++;
if(x<y)swap(x,y);
if(x%(y+1)==0)solve(x/(y+1),y);
}
int main()
{
int t;
scanf("%d",&t);
int ca=1;
while(t--)
{
ll n,m;
scanf("%lld%lld",&n,&m);
ll g=gcd(n,m);
n=n/g;
m=m/g;
if(n<m)
swap(n,m);
ans=1;
while(n%(m+1)==0)
{
ans++;
n=n/(m+1);
if(n<m)
swap(n,m);
}
printf("Case #%d: %d\n",ca++,ans);
}
return 0;
}
B - Binary Tree
t 组样例 n k
组成一个数为n 开始是0 到第k层
对每个节点 你可以为+ 也可以为-
输出数字和符号
有一个条件是 n<=2^k 所以链是可以确定下来的 就最左边的 或者最左边然后最后个取右边的
然后确定正负 大了就减掉小了就+ 也不知道为什么
#include<stdio.h>
#include<string.h>
#include<algorithm>
#include<string>
#include<iostream>
#include<math.h>
#include<map>
#include<set>
#include<queue>
using namespace std;
#define MAXN 70
#define ll long long
#define exp 1e-8
#define inf 1000000007
ll z[MAXN];
char s[MAXN];
int main()
{
int t;
scanf("%d",&t);
int ca=1;
while(t--)
{
ll n,k;
scanf("%lld%lld",&n,&k);
if(n%2==1)
{
z[0]=1;
for(int i=1;i<k;i++)
z[i]=z[i-1]*2;
ll ans=z[k-1];
s[k-1]='+';
for(int i=k-2;i>=0;i--)
{
if(ans<n)
{
s[i]='+';
ans=ans+z[i];
}
else
{
ans=ans-z[i];
s[i]='-';
}
}
}
else
{
z[0]=1;
for(int i=1;i<k-1;i++)
z[i]=z[i-1]*2;
z[k-1]=z[k-2]*2+1;
ll ans=z[k-1];
s[k-1]='+';
for(int i=k-2;i>=0;i--)
{
if(ans<n)
{
s[i]='+';
ans=ans+z[i];
}
else
{
ans=ans-z[i];
s[i]='-';
}
}
}
printf("Case #%d:\n",ca++);
for(int i=0;i<k;i++)
printf("%lld %c\n",z[i],s[i]);
}
return 0;
}
C - Five Dimensional Points
n 然后n个五维点 求对i这个点 要求其他任意2个和这个组成的角度 要不是锐角
显然n^3 那就GG
从二维入手 5个点能成功 1个 三维 7个点 1个 然后 5... 小于11就暴力
#include<stdio.h>
#include<string.h>
#include<algorithm>
#include<string>
#include<iostream>
#include<math.h>
#include<map>
#include<set>
#include<queue>
using namespace std;
#define MAXN 70
#define ll long long
#define exp 1e-8
#define inf 1000000007
int z[1010][6];
bool vis[1010];
double pi = atan(1.0)*4;
int main()
{
int n;
while(scanf("%d",&n)!=EOF)
{
memset(vis,0,sizeof(vis));
for(int i=1;i<=n;i++)
{
for(int j=1;j<=5;j++)
scanf("%d",&z[i][j]);
}
if(n>11)
printf("0\n");
else
{
int cnt=0;
for(int i=1;i<=n;i++)
{
int ok=0;
for(int j=1;j<=n;j++)
{
if(i==j)
continue;
for(int k=1;k<=n;k++)
{
if(i==k||j==k)
continue;
int x[6],y[6];
double ans=0,x1,y1;
x1=y1=0;
for(int kk=1;kk<=5;kk++)
{
x[kk]=z[j][kk]-z[i][kk];
y[kk]=z[k][kk]-z[i][kk];
ans=ans+x[kk]*y[kk];
x1=x1+x[kk]*x[kk];
y1=y1+y[kk]*y[kk];
}
x1=sqrt(x1);
y1=sqrt(y1);
ans=ans/x1/y1;
double c=acos(ans);
if(c>=0&&c<pi/2)
ok=1;
}
}
if(ok==0)
{
vis[i]=1;
cnt++;
}
}
printf("%d\n",cnt);
for(int i=1;i<=n;i++)
if(vis[i])
printf("%d\n",i);
}
}
return 0;
}
D - Arpa and a list of numbers
n x y 然后n个数
花费x 删除一个数 y 使得1个数+1 求最小的花费 使得里面的数 的gcd>1
1 发现怎么弄都不行
2公约数 一定是个p p为素数 或者p^k
先枚举 p 那么自然可以想到对于 a 这个数是删掉还是变成 p*d 根据x 和 y 就可以做出选择
目前时间似乎是 n*sum(n/p);
3 然后要求下前缀 ai 的范围 给了提示 4 求num[i]*i 的前缀 然后 对于删去的 (sum[ d] -sum[j])*x 对于+ x*(p[j]-p[d+1]);
下标注意下
#include<stdio.h>
#include<string.h>
#include<algorithm>
#include<string>
#include<iostream>
#include<math.h>
#include<map>
#include<set>
#include<queue>
using namespace std;
#define MAXN 1000010
#define ll long long
#define exp 1e-8
#define inf 1000000007
bool vis[MAXN];
int prim[MAXN];
ll p[MAXN*2+10];
ll num[MAXN*2+10];
int main()
{
for(int i=2;i<=1010;i++)
{
if(!vis[i])
for(int j=i*i;j<MAXN;j+=i)
{
vis[j]=1;
}
}
int cnt=0;
for(int i=2;i<MAXN;i++)
if(!vis[i])
prim[cnt++]=i;
int n,x,y;
while(scanf("%d%d%d",&n,&x,&y)!=EOF)
{
memset(num,0,sizeof(num));
memset(p,0,sizeof(p));
for(int i=1;i<=n;i++)
{
int a;
scanf("%d",&a);
num[a]++;
}
for(int i=1;i<=MAXN*2;i++)
{
p[i]=p[i-1]+(ll)i*num[i];
num[i]=num[i]+num[i-1];
}
int b=x/y;
ll mi=1e19;
int cnt1=0;
for(int i=0;i<cnt;i++)
{
ll ans=0;
for(int j=0;j<MAXN;j+=prim[i])
{
int c=j+prim[i];
int a,d;
a=c-b-1;
int k;
if(a<=j)
a=j;
k=num[c]-num[a];
d=j;
ans=ans+(num[a]-num[d])*x+((ll)k*c-(p[c]-p[a]))*y;
}
mi=min(ans,mi);
}
printf("%lld\n",mi);
}
return 0;
}