比赛地址
[B]Quadratic equation
题意
给定两个不定方程
x+y \equiv (a \mod p)
xy \equiv (b \mod p)
求解x，y
0 \leq x,y \leq p
题解
根据x，y的范围，由第一个方程可知，x+y共有两种取值可能，然后消元，代入第二个方程中，得到了一个二次同余方程。利用模意义下开根求解即可。
代码
#include<cstring>
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<vector>
#include<cmath>
#include<map>
using namespace std;
long long int p = 1000000007;
long long int mi(long long int a, long long int n) {
if (n == 0) return 1;
if (n == 1) return a;
long long int m = mi(a, n/2) % p;
m = m * m % p;
if (n%2) m = m * a % p;
return m;
}
long long int modpow(long long int a, long long int b, long long int n) {
long long int d = 1, i = 0;
while(b >= ((1LL)<<i)) i++;
for (--i; i >= 0; --i) { d = d*d%n; if (b&(1LL<<i)) d = d*a%n; }
return d;
}
long long int modsqrt(long long int a, long long int n) {
long long int b, k, i, x;
if (n == 2) return a%n;
if (modpow(a, (n-1)/2, n) == 1) {
if (n%4==3) x = modpow(a, (n+1)/4, n); else {
for (b = 1; modpow(b, (n-1)/2, n) == 1; b++);
i = (n-1)/2; k=0; do { i/=2; k/=2;
if ((modpow(a, i, n)*modpow(b, k, n)+1)%n == 0) k += (n-1)/2;
} while(i%2==0);
x = (modpow(a, (i+1)/2, n)*modpow(b, k/2, n)) % n;
} if (x*2 > n) x = n-x; return x;
} return -1;
}
int main() {
long long int b, c;
int T; cin >> T; while(T--) {
cin >> b >> c;
long long int delta = ((b*b%p - 4*c%p) + p) % p;
long long int genhao = modsqrt(delta, p);
if (delta == 0) {
long long int x = b * mi(2, p-2) % p ;
cout << x << " " << x << endl;
} else if (genhao < 0) {
cout << "-1 -1\n";
} else {
long long int x1, x2;
x1 = (b-genhao+p)%p*mi(2, p-2)%p;
x2 = (b - x1 + p)%p;
if (x1 <= x2) cout << x1 << " " << x2 << endl;
else cout << x2 << " " << x1 << endl;
}
}
}
[D]Knapsack Cryptosystem
题意
给定一个长度为n的序列和一个数sum。求一种选数方案，使得从这n个数中选出的这些数的总和是sum。
该序列根据Merkle–Hellman knapsack cryptosystem加密方式得到，所以答案唯一。
题解
折半搜索
代码
#include<cstring>
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<vector>
#include<cmath>
#include<bitset>
#include<map>
#define N 200010
#define l(x) (x<<1)
#define r(x) ((x<<1)+1)
#define LL unsigned long long
#define INF 0x3f3f3f3f
using namespace std;
LL n,i,j,top;
LL a[40];
LL s,sum,ss;
map <LL,LL> M;
int main(){
scanf("%d%llu",&n,&sum);
for (i=1;i<=n;i++) scanf("%llu",&a[i]);
top=(n<=18)?n:18;
for (i=1;i<=(1<<top);i++){
s=0;
for (j=0;j<top;j++) if ((1<<j)&i) s+=a[j+1];
M[s]=i;
}
if (n<=top){
for (i=0;i<n;i++) printf(((1<<i)&M[sum])?"1":"0");
return 0;
}
ss=n-top;
for (i=1;i<(1<<ss);i++){
s=0;
for (j=0;j<ss;j++) if ((1<<j)&i) s+=a[top+j+1];
if (M[sum-s]) {
for (j=0;j<top;j++) printf(((1<<j)&M[sum-s])?"1":"0");
for (j=0;j<ss;j++) printf(((1<<j)&i)?"1":"0");
return 0;
}
}
return 0;
}
[E]All men are brothers
题意
一开始有n个人，两两之间互不认识。每次有一个操作，会让两个人建立认识的关系。这种关系具有传递性。求每次操作以后有多少种选人方案，使得选出的四个人两两之间都不认识。
题解
拿并查集维护认识关系以及连通块大小。然后每次操作，用容斥原理更新从所有人中选出两个人互不认识的方案以及答案数即可。
代码
#include<cstring>
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<vector>
#include<cmath>
#include<map>
#define N 200020
#define l(x) (x<<1)
#define r(x) ((x<<1)+1)
#define LL unsigned long long
#define INF 0x3f3f3f3f
using namespace std;
LL n,m,i,x,y;
LL A,B;
int f[N];
LL size[N];
LL Ans,sum,cnt;
inline LL read(){
LL p=0; char c=getchar();
while (c<48||c>57) c=getchar();
while (c>=48&&c<=57) p=(p<<1)+(p<<3)+c-48,c=getchar();
return p;
}
inline int Find(int x){return (x==f[x])?x:f[x]=Find(f[x]);}
int main(){
n=read(); m=read();
if (n<4){
for (i=1;i<=m+1;i++) printf("0\n");
return 0;
}
for (i=1;i<=n;i++) f[i]=i,size[i]=1;
Ans=(LL)n*(n-1)/2; sum=(LL)n*(n-1)/2;
Ans=Ans*(n-2)/3; Ans=(Ans*(n-3))/4;
printf("%llu\n",Ans);
for (i=1;i<=m;i++){
x=read(); y=read();
x=Find(x); y=Find(y);
if (x==y){
printf("%llu\n",Ans);
continue;
}
A=size[x]; B=size[y];
cnt=sum-A*(n-A)-B*(n-B)+A*B;
Ans-=cnt*A*B; sum-=A*B;
printf("%llu\n",Ans);
f[x]=y; size[y]+=size[x];
}
return 0;
}
[J]Symmetrical Painting
题意
给定一系列分布在坐标轴上的矩形，矩形的宽度为1，高度给定。现在需要使整个图形变为一个关于水平的对称图形，求最多能够留下多少个矩形块。
题解
签到题
代码
#include<cstring>
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<vector>
#include<cmath>
#define N 900010
#define l(x) (x<<1)
#define r(x) ((x<<1)+1)
#define LL long long
#define INF 0x3f3f3f3f
using namespace std;
int n,i,cnt;
LL s,sum,Ans,l,r,mid;
struct Data{
LL l;
int f;
}a[N];
inline int Abs(int x){return (x<0)?-x:x;}
inline void Swap(int &a,int &b){a^=b^=a^=b;}
inline LL Min(LL a,LL b){return (a<b)?a:b;}
inline LL Max(LL a,LL b){return (a>b)?a:b;}
inline int read(){
int p=0; char c=getchar();
while (c<48||c>57) c=getchar();
while (c>=48&&c<=57) p=(p<<1)+(p<<3)+c-48,c=getchar();
return p;
}
inline bool cmp(const Data x,const Data y){return x.l<y.l;}
int main(){
scanf("%d",&n);
for (i=1;i<=n;i++){
scanf("%lld%lld",&l,&r);
l*=2; r*=2; mid=(l+r)>>1;
a[++cnt].l=l; a[cnt].f=1;
a[++cnt].l=r; a[cnt].f=1;
a[++cnt].l=mid; a[cnt].f=-2;
}
sort(a+1,a+1+cnt,cmp);
s=0; sum=Ans=0;
for (i=1;i<cnt;i++){
s+=a[i].f;
sum+=s*(a[i+1].l-a[i].l);
Ans=(sum>Ans)?sum:Ans;
}
printf("%lld\n",Ans);
return 0;
}
总结&吐槽
这次是数学专场，打的很惨。
D题按照之前打CF的经验，看了半天Wikipedia,然后思路就被带歪了，到最后也没反应过来是折半搜索。B题幸亏有交大的模板，才能按照这个思路写下去。(听说其他人都是用什么二次剩余和原根做的，这些方法都这么普遍吗QAQ)E题推了一会式子就写完了，并不是很难。
估计积分排名要掉了，希望之后的场次不要有出题出的这么畸形的了。
没有抽到抱枕，不开心
声明:
本文采用
BY-NC-SA
协议进行授权，如无注明均为原创，转载请注明转自
Marvolo
本文地址: ACM暑期集训第五场
本文地址: ACM暑期集训第五场
