12.22改题
Point_Nine
·
·
个人记录
T1
```cpp
//无非是几个端点,然后有一些点的值相同
//考虑怎么DP
//dp[i][j(0-9)]表示前缀和为0,9的方案数
//考虑转移矩阵
/*
2 1 1 1 1 1 1 1 1
1 2 1 1 1 1 1 1 1
1 1 2 1 1 1 1 1 1
1 1 1 2 1 1 1 1 1
1 1 1 1 2 1 1 1 1
1 1 1 1 1 2 1 1 1
1 1 1 1 1 1 2 1 1
1 1 1 1 1 1 1 2 1
1 1 1 1 1 1 1 1 2
*/
//自乘一遍
/*
12 11 11 11 11 11 11 11 11
11 12 11 11 11 11 11 11 11
11 11 12 11 11 11 11 11 11
11 11 11 12 11 11 11 11 11
11 11 11 11 12 11 11 11 11
11 11 11 11 11 12 11 11 11
11 11 11 11 11 11 12 11 11
11 11 11 11 11 11 11 12 11
11 11 11 11 11 11 11 11 12
*/
//再乘一遍
/*
112 111 111 111 111 111 111 111 111
111 112 111 111 111 111 111 111 111
111 111 112 111 111 111 111 111 111
111 111 111 112 111 111 111 111 111
111 111 111 111 112 111 111 111 111
111 111 111 111 111 112 111 111 111
111 111 111 111 111 111 112 111 111
111 111 111 111 111 111 111 112 111
111 111 111 111 111 111 111 111 112
*/
//数学归纳法如果不同的话就是...100+10+1
//数学归纳法如果相同的话就是...100+10+1+1
//然后转化为Q个物品,存在左右端点
//分成九组,(0-8)表示这两个端点是一样的
//还有一些限制条件,首先每种分组方案的基础分是1
//还有某些条件一些系数显然的事情是
//这个式子在这摆着不变,多的只是一些变化罢了
//无非就是分三个子集转移罢了
//表示这一步下一步上一步
//计算所有的分组方案的得分即可
//大概的DP方程也就是这样
//dp[S]+=dp[S^T]*1*(T_add's point)
//但是我并不是很想写...
//考虑端点重合的情况
//可以看成a1=a2,a2=a3,a1=a3
//可以合并为一个连通块
//显然的事情,原式子不变,某些式子变成1
//一些东西一起变
//我会了
#include<bits/stdc++.h>
#define int long long
#define mod 1000000007
#define MAXN 110000
using namespace std;
int poz[MAXN],bc[MAXN],fa[MAXN],ZF[MAXN],cnt,tot,Sum,Ans,N,Q,St,dp[1<<18];
set<int>Link[MAXN];
map<int,int>mp;
int Find(int x)
{
if(fa[x]==x) return x;
return fa[x]=Find(fa[x]);
}
struct node
{
int l,r;
}que[MAXN];
int my_pow(int a,int b)
{
int res=1;
while(b)
{
if(b&1)
{
res=(res*a)%mod;
}
a=(a*a)%mod;
b>>=1;
}
return res;
}
int sol(int T)
{
vector<int>Mid;
for(int i=1;i<=Sum;i++)
{
if((T>>(i-1))&1)
{
for(set<int>::iterator it=Link[i].begin();it!=Link[i].end();it++)
{
Mid.push_back(*it);
}
}
}
int res=1;
sort(Mid.begin(),Mid.end());
for(int i=1;i<Mid.size();i++)
{
if(abs(mp[Mid[i]]-mp[Mid[i-1]])==1)
{
res=(res*((my_pow(10,abs(Mid[i]-Mid[i-1]))+8)%mod*my_pow((my_pow(10,abs(Mid[i]-Mid[i-1]))-1),mod-2)%mod))%mod;
}
}
return res;
}
signed main()
{
cin>>N>>Q;
for(int i=1;i<=N;i++) fa[i]=i;
for(int i=1;i<=Q;i++)
{
cin>>que[i].l>>que[i].r;
poz[++cnt]=que[i].l;
poz[++cnt]=que[i].r;
int fl=Find(que[i].l);
int fr=Find(que[i].r);
if(fl!=fr)
{
fa[fr]=fl;
}
}
sort(poz+1,poz+1+cnt);
for(int i=1;i<=cnt;i++)
{
if(!mp[poz[i]])
{
mp[poz[i]]=++tot;
bc[tot]=poz[i];
}
}
St=my_pow(10,bc[1]);
St=(St*my_pow(10,N-bc[tot]))%mod;
for(int i=2;i<=tot;i++)
{
St=(((St*my_pow(10,bc[i]-bc[i-1]))%mod)*my_pow(9,mod-2))%mod;
}
//枚举连通块罢了
for(int i=1;i<=N;i++)
{
if(Find(i)==i) Sum++,ZF[fa[i]]=Sum;
}
for(int i=1;i<=Q;i++)
{
if(Find(que[i].l)==que[i].l) Sum++,ZF[fa[que[i].l]]=Sum;
if(que[i].l!=que[i].r&&Find(que[i].r)==que[i].r) Sum++,ZF[fa[que[i].r]]=Sum;
}
for(int i=1;i<=Q;i++)
{
Link[ZF[fa[que[i].l]]].insert(que[i].l);
if(que[i].l!=que[i].r) Link[ZF[fa[que[i].r]]].insert(que[i].r);
}
// for(int i=1;i<=Sum;i++)
// {
// for(set<int>::iterator it=Link[i].begin();it!=Link[i].end();it++)
// {
// cout<<"*it "<<*it<<" ";
// }
// cout<<endl;
// }
dp[0]=1;
for(int i=0;i<=8;i++)
{
for(int S=0;S<=(1<<Sum)-1;S++)
{
for(int T=S;T;T=(T-1)&S)
{
dp[S]=(dp[S]+dp[S^T]*sol(T))%mod;
}
}
}
int Ans=(dp[(1<<Sum)-1]*St)%mod;
cout<<Ans<<endl;
}
```
正确代码
```cpp
#include<bits\stdc++.h>
using namespace std;
#define int long long
const int Maxn = 40;
const int Maxs = 1 << 17;
const int P = 1000000007;
inline int Pow(int x , int y , int res = 1){
while(y){
if(y & 1) res *= x;
x *= x;
res %= P;
x %= P;
y >>= 1;
}
return res;
}
int n;
int q;
struct Q{
int x;
int y;
Q(){}
Q(int a , int b){
x = a;
y = b;
}
}a[Maxn] , lim[Maxn];
int be[Maxn];
int c[Maxn];
int A[Maxn];
int B[Maxn];
int id[Maxn];
int tot;
int fa[Maxn];
inline int find(int x){
return fa[x] == x ? x : fa[x] = find(fa[x]);
}
inline void merge(int x , int y){
int fx = find(x);
int fy = find(y);
if(fx != fy){
fa[fx] = fy;
}
}
int dp[Maxs];
int f[Maxs];
int val[Maxs];
inline int lowbit(int x){
return x & -x;
}
int work(int n , int m){
for(int i = 1 ; i < (1 << n) ; i++){
val[i] = 1;
for(int j = 1 ; j <= m ; j++){
if((i & (1 << (lim[j].x - 1))) && (i & (1 << (lim[j].y - 1)))){
val[i] = val[i] * B[j] % P;
}
}
}
for(int i = 1 ; i < (1 << n) ; i++){
f[i] = val[i];
int st = i - lowbit(i);
for(int j = st ; j ; j = (j - 1) & st){
f[i] = (f[i] - f[i ^ j] * val[j] % P + P) % P;
}
}
for(int i = 0 ; i < (1 << n) ; i++){
f[i] *= 9;
f[i] %= P;
}
dp[0] = 1;
for(int i = 1 ; i < (1 << n) ; i++){
dp[i] = f[i];
int st = i - lowbit(i);
for(int j = st ; j ; j = (j - 1) & st){
dp[i] += dp[j] * f[i ^ j] % P;
dp[i] %= P;
}
}
int ans = Pow(9 , P - 2) * dp[(1 << n) - 1] % P;
for(int i = 1 ; i <= m ; i++){
ans = ans * A[i] % P;
}
return ans;
}
signed main(){
cin >> n >> q;
for(int i = 1 ; i <= q ; i++){
int x , y;
cin >> x >> y;
a[i] = Q(x - 1 , y);
c[++tot] = x - 1;
c[++tot] = y;
}
sort(c + 1 , c + tot + 1);
tot = unique(c + 1 , c + tot + 1) - c - 1;
for(int i = 1 ; i <= tot ; i++) fa[i] = i;
for(int i = 1 ; i <= q ; i++){
int x = lower_bound(c + 1 , c + tot + 1 , a[i].x) - c;
int y = lower_bound(c + 1 , c + tot + 1 , a[i].y) - c;
merge(x , y);
}
int cnt = 0;
for(int i = 1 ; i <= tot ; i++){
int fx = find(i);
if(fx == i) id[i] = ++cnt;
}
cout<<cnt<<endl;
for(int i = 2 ; i <= tot ; i++){
A[i - 1] = Pow(9 , P - 2) * (Pow(10 , c[i] - c[i - 1]) + P - 1) % P;
B[i - 1] = (Pow(A[i - 1] , P - 2) + 1) % P;
int x = id[find(i - 1)];
int y = id[find(i)];
lim[i - 1] = Q(x , y);
}
if(q == 0) cout << Pow(10 , n);
cout << work(cnt , tot - 1) * Pow(10 , n - c[tot] + c[1]) % P;
return 0;
}
```
$T3
//考场上造出来了20pts
/*
20pts代码
#include<bitsdc++.h>
using namespace std;
bool vis[1100][1100];
int main()
{
int R,B,Ans=0;
cin>>R>>B;
if(R==B)
{
int ed,num=0;
for(ed=1;ed;ed++)
{
num=(ed+1)*ed/2;
if(num>R) break;
Ans+=ed+1;
R-=(ed+1)*ed/2;
B-=(ed+1)*ed/2;
}
Ans+=(2*R/ed);
cout<<Ans<<endl;
}
*/
//基本思想是懂的
//先考虑二分一个答案
//然后选出K个点,使得选出来的X,Y尽可能小
//至于为什么二分,显然的想一想
//因为直接贪心不好贪,那就二分答案+判定比较好写
//考虑已知选出来几个点,那么就可以构造出选K个点的最优方案
//然后判断能不能满足R,B的大小即可
//显然的事情,X与Y反比关系,那么一定是个凸壳
//那么维护凸壳上的点然后判断R,B是否在凸壳内部就可以了
//那么具体实现不太会
//如何构造出凸壳上的点
//最后的凸壳上的点肯定都能表示成px+qy
//貌似也很显然,他们按一定比率选择的时候是较优的
//而且是贪心的选,那么肯定是凸壳上的点
//以后发现无法直接贪心考虑转判定比较好
#include<bits/stdc++.h>
#define int long long
using namespace std;
int sol(int n,int a,int b,int m)
{
//不要推式子(wuwuwu)
//px+qy<=z
if(a>=m) return n*(a/m)+sol(n,a%m,b,m);
else if(b==0) return n*(a/m);
else if(b>=m) return n*(n-1)/2*(b/m)+sol(n,a,b%m,m);
else return sol((a+b*n)/m,(a+b*n)%m,m,b);
}
pair<int,int> Find(int k,int x,int y)
{
//传参(选出k个点,p,q)
//知道斜率给他搞出来目前这个凸壳上的点
int r=sqrt(2*k*(double)x*(double)y);
int l=max(0ll,r-x-y-1);
int ans;
//这个就很显然了,你可定两个x,y选择的上界
//我想的是枚举,但显然二分上界更简单
//这个二分是Z,求出
while(l<=r)
{
int mid=(l+r)>>1;
int cnt=sol(mid/x+1,mid%x,x,y)+(mid/x+1);
//二分上界Z,求出最小的Z,求出X,Y
if(cnt>=k)
{
ans=mid;
r=mid-1;
}
else l=mid+1;
}
int X=0,Y=0;
for(int i=0;i*x<=ans;i++)
{
int c=(ans-i*x)/y+1;
X+=c*i;
Y+=c*(c-1)/2;
}
return make_pair(X,Y);
}
bool check(int K,int X,int Y)
{
//传参(选几个,目前有X个红球,Y个篮球)
//转为判定
pair<int,int> ans=make_pair(-1,-1);
pair<int,int> Mid_ans=ans;
int tot=1e9+7;
int l=0,r=tot;
//已知的是,咱们现在要确定p,q
//由于是比率关系,需要知道该比率的p,q对应的最优解
//另一个显然的事情,我们需要知道凸壳上的点
//那就二分斜率,斜率有比率确定,然后来这里搞一个凸壳
while(l<=r)
{
int mid=(l+r)>>1;
//这个有单调性,故可以二分
//那么既然有了p,q,那么可以选出点产生凸壳上一个点
//那么可以由这个点分4个区域
//看在哪边,然后取另一侧二分得到
//可以预见的是,这个东西必然可以找到一个确定的点把他确定位置
//也就相当于在凸壳上二分了
pair<int,int> now=Find(K,tot-mid,mid);
if(now.first<=X&&now.second<=Y) return 1;
if(now.first>=X&&now.second>=Y) return 0;
if(now.first<X) l=mid+1,ans=now;
else Mid_ans=now,r=mid-1;
}
//也就是相当于判断在这条直线的上面或下面
return ans.second*(Mid_ans.first-X)+Mid_ans.second*(X-ans.first)<=Y*(Mid_ans.first-ans.first);
}
signed main()
{
int R,B;
cin>>R>>B;
if(R<B) swap(R,B);
int l=3,r=2000000,Ans;
while(l<=r)
{
int mid=(l+r)>>1;
if(check(mid,R,B))
{
l=mid+1;
Ans=mid;
}
else r=mid-1;
}
cout<<Ans-1<<endl;
}