A - City:
直接推公式，一开始以为要用大数，其实不用。
组合数。
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int main()
{
int n,m;
while(scanf("%d%d",&n,&m)!=EOF)
{
ll ans=0,a=0,b=0;
for(int i=2;i<=n;i+=2)
a+=(n-i+1);
for(int j=2;j<=m;j+=2)
b+=(m-j+1);//cout<<b<<endl;
ans=a*(m+1)+b*(n+1);
for(int i=2;i<=n;i++)
ans+=b*(i/2)*2;
printf("%lld\n",ans);
}
return 0;
}
M - Value：
思路：二进制状压暴力
从2开始，每当找到一个最小的底数，就把他所有允许范围内的所有指数全部枚举完，二进制的形式描述各种指数对应的数是否存在于集合A中，然后枚举各种情况，求出最大值，加入集合A中。
这种枚举方法比较常用，记住!
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e5+5;
int a[N],b[N];
int num[50];
bool vis[N];
ll ans;
void solve(int m)
{
ll maxn=0;
for(int i=1;i<(1<<m);i++)//二进制枚举
{
ll sum=0;
for(int j=0;j<m;j++)
{
if(i&(1<<j))
{
sum+=a[num[j]];
int p=j+1;
for(int k=p+p;k<=m;k+=p)//注意理清楚倍数关系
if(i&(1<<(k-1)))
sum-=b[num[k-1]];
}
}
maxn=max(maxn,sum);
}
ans+=maxn;//cout<<"------"<<endl;
}
int main()
{
int n;
scanf("%d",&n);
for(int i=1;i<=n;i++)
scanf("%d",&a[i]);
for(int i=1;i<=n;i++)
scanf("%d",&b[i]);
ans=a[1];
memset(vis,0,sizeof(vis));
for(int i=2;i<=n;i++)
{
if(!vis[i])
{
int x=0;
for(ll j=i;j<=n;j*=i)//int: re
{
num[x++]=j;
vis[j]=1;
}
solve(x);
}
}
printf("%lld\n",ans);
return 0;
}
H - King：
随机化法
完全没有想过用这种方法解题。QWQ
因为我们要找是否存在长度大于 n/2 ，所以我们随机选择两个数字，这两个数字出现在答案序列中的概率至少为 1/4 ，如果我们选择多次，那么答案的正确性为：1 - (3/4)^x，当x比较大的时候是可以保证正确率的。
但是现在选择的两个数字可能差距了几个公比，怎么办呢？我随机两个相邻的数字即可。什么意思呢？就是我们令当前随机出来的两个数字是答案中相邻的数字，可以证明最小的距离最大值是不会超过2的，所以直接判断x,x+1和x,x+2即可，都判断一次。
一直WA在了test 18，用别人一样思路的代码可以过，经过长时间的对比(><)发现原来是随机数的问题。我一开始用的是rand()产生的随机数，发现别人用的都是用
mt19937来输出随机数。
它是C++11中新加入的新特性，是一种随机数算法，用法与rand()函数类似，但是具有速度快，周期长的特点(它的名字便来自周期长度：2^19937-1)，说的直白一点，我们都知道rand()在windows下生成的数据范围为0-32767(数太小了)，但是这个函数的随机范围大概在(−maxint,+maxint)(maxint为int类型最大值)。
用法：
#include<bits/stdc++.h>
using namespace std;
int main() {
mt19937 mt_rand(time(0));
cout << mt_rand() << endl;
return 0;
}
AC代码：（本地编译过不了，要改为C++11标准）
#include <bits/stdc++.h>
#include <chrono>
#include <random>
using namespace std;
typedef long long ll;
const int N=2e5+5;
ll b[N],inv[N];
ll qpow(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%mod;
}
void init(ll p,int n)
{
for(int i=1;i<=n;i++)
inv[i]=qpow(b[i],p-2,p);
}
int solve(int x,int y,ll p,int n)
{
ll q=b[y]*inv[x]%p;
int last=x,ans=2;
for(int i=x-1;i>=1;i--)
{
if(b[last]*inv[i]%p==q)
{
ans++;
last=i;
}
}
int pre=y;
for(int i=y+1;i<=n;i++)
{
if(b[i]*inv[pre]%p==q)
{
ans++;
pre=i;
}
}//cout<<"ans="<<ans<<endl;
return ans;
}
int main()
{
int t;
scanf("%d",&t);
mt19937 mt_rand(time(0));
while(t--)
{
int n,ans=0,tt=-1;
ll p;
scanf("%d%lld",&n,&p);
for(int i=1;i<=n;i++)
scanf("%lld",&b[i]);
init(p,n);
for(int i=1;i<=150;i++)//足够的迭代次数
{
int x=mt_rand()%(n-1)+1;
for(int i=x+1;i<=n&&i<=x+2;i++)
ans=max(ans,solve(x,i,p,n));
}
printf("%d\n",ans>=(n+1)/2?ans:tt);
}
return 0;
}
E - Flow：
1.总的边权值得和不变，所以最终的最大流量值是固定的，而初始的流量也已知，所以可以求出增量。
2.整个过程就相当于平均化边权，因此只管把小于平均值得边权加上去就行。
3.要使流量+1，可能需要修改多条边。
4.注意两个点的情况，和所有边权都相等的情况。
#include <bits/stdc++.h>
using namespace std;
const int N=1e5+5;//
typedef long long ll;
typedef pair<int,int> P;
vector<P> pic[N],edge;
priority_queue<int,vector<int>,greater<int> >que;
int main()
{
int n,m;
while(scanf("%d%d",&n,&m)!=EOF)
{
int x,y,z;
ll sum=0,res=0;//所有的边的总长度
for(int i=0;i<=n;i++)
pic[i].clear();
while(!que.empty())
que.pop();
edge.clear();
for(int i=1;i<=m;i++)
{
scanf("%d%d%d",&x,&y,&z);
pic[x].push_back(make_pair(y,z));
sum+=z;
}
int len=0,p=1;//len:路径长度
while(p!=n)
{
len++;
p=pic[p][0].first;
}
if(len==1)
{
printf("0\n");
continue;
}
sum/=len;//最终的最大流量（平均）
for(int i=0;i<pic[1].size();i++)//遍历每一条路径
{
P now=pic[1][i];
p=now.first;
que.push(now.second);
while(p!=n)//把每条路径的所有边入队排序
{
now=pic[p][0];
que.push(now.second);
p=now.first;
}
int tp=que.top();
int cnt=1;
que.pop();
res+=tp;//初始时刻的流量（每条路径的最短边的容量和）
while(!que.empty())
{
edge.push_back(make_pair(cnt++,que.top()-tp));//次序，差值
tp=que.top();
que.pop();
}
}
sum-=res;//需要的增量
sort(edge.begin(),edge.end());//先按在路径中的次序然后按差值大小进行排序
p=0;
ll ans=0;
while(sum>=edge[p].second&&p<edge.size())//注意：如果所有边的权值都相等，那么那么p<dege.size()这个限制条件，会re
{//找了好久才发现的错误
ans+=(1LL)*edge[p].first*edge[p].second;//要修改多条边
sum-=edge[p].second;
p++;
if(sum==0)
break;
}
ans+=(1LL)*edge[p].first*sum;
printf("%lld\n",ans);
}
return 0;
}
C - Dirichlet k-th root：
狄利克雷卷积性质：
快速幂&卷积:
如果 f在模 mod下进行 k次卷积得到 g，那么 g进行 inv(k)次卷积后就会得到 f。
（目前不会证明）
这种方法待学：推荐题解
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e5+5;
const int p=998244353;
ll g[N],f[N],t[N];
void read(ll &x)
{
char cc;
int f=1;
cc=getchar();
while(cc<'0'||cc>'9')
{
if(cc=='-')
f=-1;
cc=getchar();
}
while(cc>='0'&&cc<='9')
{
x=10*x+cc-'0';
cc=getchar();
}
x=x*f;
}
ll power(ll a,ll b)
{
ll res=1;
while(b)
{
if(b&1)
res=res*a%p;
a=a*a%p;
b>>=1;
}
return res%p;
}
void mul(ll a[],ll b[],int n)
{
memset(t,0,sizeof(t));
/*for(int i=1;i<=n;i++):Time limit exceeded on test 26 牛客:599ms { for(int j=i;j<=n;j+=i) t[j]=(t[j]+a[i]*b[j/i]%p)%p; }*/
/*for(int i=1;i<=n;i++):936ms { for(int j=1;j*i<=n;j++) t[i*j]=(t[i*j]+a[i]*b[j]%p)%p; }*/
for (int i=1;i*i<=n;i++) {//686ms
t[i*i]=(t[i*i]+a[i]*b[i]%p)%p;
for (int j=i+1;i*j<=n;j++) {
t[i*j]=(t[i*j]+a[i]*b[j]%p+a[j]*b[i]%p)%p;
}
}
for(int i=1;i<=n;i++)
a[i]=t[i];
}
void qpow(ll a[],ll b,int n)
{
f[1]=1;
while(b)
{
if(b&1)
mul(f,a,n);
mul(a,a,n);
b>>=1;
}
}
int main()
{
int n,k;
scanf("%d%d",&n,&k);
for(int i=1;i<=n;i++)
{
read(g[i]);
f[i]=0;
}
ll inv=power((ll)k,(ll)p-2);//k的逆元
qpow(g,inv,n);
for(int i=1;i<=n;i++)
printf("%lld%c",f[i],i==n?'\n':' ');
return 0;
}
京公网安备 11010502036488号