【比赛报告】2018.10.22校赛[【Nescafé 18】杯模拟赛] NOIP练习赛十八
比赛时间:2018.10.22 选手:lrllrl 得分:100+0+0=100 用时:2h
首先判断可行性很好办,看能不能整除就好了。
我们单独考虑行(无环情况下)。
设每行 的目标摊位数目为 , 的前缀和为 ,即
最少步数为
设 , 变成 的前缀和,即
最少步数为
现在考虑环的情况。假设从 位置之后断开写成一行,前缀和为:
可以发现 ,则答案为 ,显然 为中位数时有最小值。
同理可得列的情况。
#include<cstdio>
#include<algorithm>
#include<cmath>
using namespace std;
typedef long long ll;
const int N=1e5+10;
int n,m,t;
ll r[N],c[N],sumr[N],sumc[N],ansr,ansc;
int main()
{
//freopen("tanabata.in","r",stdin);
//freopen("tanabata.out","w",stdout);
scanf("%d%d%d",&n,&m,&t);
for(int i=1,x,y;i<=t;i++)
scanf("%d%d",&x,&y),r[x]++,c[y]++;
if(t%n!=0&&t%m!=0)
puts("impossible");
else if(t%n==0&&t%m==0)
{
for(int i=1;i<=n;i++)
sumr[i]=sumr[i-1]+r[i]-t/n;
for(int j=1;j<=m;j++)
sumc[j]=sumc[j-1]+c[j]-t/m;
sort(sumr+1,sumr+n+1);
sort(sumc+1,sumc+m+1);
for(int i=1;i<=n;i++)
ansr+=abs(sumr[i]-sumr[n+1>>1]);
for(int j=1;j<=m;j++)
ansc+=abs(sumc[j]-sumc[m+1>>1]);
printf("both %lld\n",ansr+ansc);
}
else if(t%n==0)
{
for(int i=1;i<=n;i++)
sumr[i]=sumr[i-1]+r[i]-t/n;
sort(sumr+1,sumr+n+1);
for(int i=1;i<=n;i++)
ansr+=abs(sumr[i]-sumr[n+1>>1]);
printf("row %lld\n",ansr);
}
else
{
for(int j=1;j<=m;j++)
sumc[j]=sumc[j-1]+c[j]-t/m;
sort(sumc+1,sumc+m+1);
for(int j=1;j<=m;j++)
ansc+=abs(sumc[j]-sumc[m+1>>1]);
printf("column %lld\n",ansc);
}
return 0;
}
#include<cstdio>
#include<cstring>
const int N=2050;
int k,n,num[N],vis[N];
bool dfs(int u,int pos)
{
if(vis[u])return false;
if(pos==n)return true;
num[pos]=u&1;vis[u]=1;
if(dfs((u<<1)&(n-1),pos+1))return true;
if(dfs((u<<1|1)&(n-1),pos+1))return true;
vis[u]=0;
return false;
}
int main()
{
while(~scanf("%d",&k))
{
n=1<<k;
memset(vis,0,sizeof(vis));
dfs(0,1);
printf("%d ",n);
for(int i=1;i<k;i++)
printf("0");
for(int i=1;i<=n-k+1;i++)
printf("%d",num[i]);
printf("\n");
}
return 0;
}
#include<cstdio>
#include<map>
#include<algorithm>
using namespace std;
typedef long long ll;
typedef map<ll,int>type;
typedef type::const_iterator trc;
#define X first
#define Y second
int t;
ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}
type divi(ll a)//唯一分解
{
type r;
for(int i=2;(ll)i*i<=a;i++)
if(a%i==0)
{
int p=0;
while(a%i==0)++p,a/=i;
r[i]=p;
}
if(a!=1)r[a]=1;
return r;
}
ll euler(ll a,const type&r)//求欧拉函数phi
{
for(trc i=r.begin();i!=r.end();i++)
if(i->Y)a=a/i->X*(i->X-1);
return a;
}
ll qmul(ll a,ll b,ll m)//快速乘,以免乘爆
{
ll ans=0,p=a%m;
while(b)
{
if(b&1)ans=(ans+p)%m;
p=(p+p)%m;
b>>=1;
}
return ans;
}
ll qpow(ll a,ll b,ll m)//快速幂
{
ll ans=1,p=a%m;
while(b)
{
if(b&1)ans=qmul(ans,p,m);
p=qmul(p,p,m);
b>>=1;
}
return ans;
}
int main()
{
//freopen("in.txt","r",stdin);
scanf("%d",&t);
while(t--)
{
ll a,b,k;
scanf("%lld%lld%lld",&a,&b,&k);
ll g=gcd(a,b);a/=g,b/=g;
type sb=divi(b),sk=divi(k);
int p1=0;ll nb=b;//p1是转化次数,即混循环之前的长度
for(trc i=sk.begin();i!=sk.end();i++)
{
int p=sb[i->X];sb[i->X]=0;
p1=max(p1,(p+i->Y-1)/i->Y);
while(p)nb/=i->X,p--;
}
ll p2;
if(nb==1)p2=0;//是个有限小数
else
{
ll eb=euler(nb,sb);//φ(nb)
p2=eb;//p2存k模b的阶,初始化为φ(nb)
sb=divi(eb);
for(trc i=sb.begin();i!=sb.end();i++)
{
int p=i->Y;
while(p)
{
if(qpow(k,p2/i->X,nb)==1)
p2/=i->X,p--;
else break;
}
}
}
printf("%d %lld\n",p1,p2);
}
return 0;
}
赛后总结
感觉这套题有点难受……暴力也不太好打。T1排序中位数T2欧拉路T3数论,质量还是很高的。