文章目錄
- A. Krypton
- D. Meaningless Sequence
- F. Strange Memory
- H. Combination Lock
- J. Abstract Painting
- K. Ragdoll
- L. Coordinate Paper
A. Krypton
二進制列舉所有情況,找最大的即可,
#include <bits/stdc++.h>
using namespace std;
int n;
int cost[7]={1,6,28,88,198,328,648};
int extra[7]={8,18,28,58,128,198,388};
int normal[7]={10,60,280,880,1980,3280,6480};
int main()
{
scanf("%d",&n);
int ans=0;
for(int i=0;i<(1<<7);++i)
{
int tmp=n;
int res=0;
int now=i;
for(int j=0;j<7;++j)
{
if(now&1)
{
tmp-=cost[j];
res+=extra[j]+normal[j];
}
now>>=1;
}
if(tmp<0)
continue;
ans=max(ans,res+tmp*10);
}
printf("%d\n",ans);
return 0;
}
D. Meaningless Sequence
我們發現,ai=(ci的二進制下1的個數),對于求和,我們只要找到對于包含i個1的情況有多少種即可,這是個組合數學問題,我們從最高位的1開始,讓其為0,那么后面可以隨便取,然后再到第二位1(0的部分可以跳過,因為在前面已經被取到了),這時候前面的第一位取1,然后后面隨意取…一直加到最后即可,
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod=1e9+7;
const int N=3e3+5;
char a[N];
ll c;
ll quickpow(ll a,ll b)
{
ll res=1;
while(b)
{
if(b&1)
res=res*a%mod;
b>>=1;
a=a*a%mod;
}
return res;
}
ll C[N][N];
int main()
{
for(int i=0;i<=3001;++i)
C[i][0]=1;
for(int i=1;i<=3001;++i)
for(int j=1;j<=i;++j)
C[i][j]=(C[i-1][j]+C[i-1][j-1])%mod;
scanf("%s",a);
scanf("%lld",&c);
ll ans=0;
ll now=0;
int len=strlen(a);
for(int i=0;i<len;++i)
{
if(a[i]=='1')
{
int up=len-i-1;
for(int j=0;j<=up;++j)
{
ans=(ans+C[up][j]*quickpow(c,j+now)%mod)%mod;
}
now++;
}
}
printf("%lld\n",(ans+quickpow(c,now))%mod);
return 0;
}
F. Strange Memory
dsu on tree(有時間寫篇博客總結一下),對于dsu on tree有兩種型別的題,一種是直接算子樹貢獻,還有一種就和這題一樣計算不同子樹間的貢獻,因為是要計算不同子樹間的貢獻,所以需要用到遞回,然后本題可以用vector過,正解是要拆位,對于要計算異或和,我們將其拆為20位,對于每一位,記錄0和1的個數,對于0來說,異或上1就會產生貢獻,所以我們只要統計每位0和1的個數即可,這樣時間復雜度為O(20nlogn),
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e5+5;
int n;
int a[N];
vector<int>g[N],temp;
int p[(1<<20)+5][20][2];
ll ans;
//ll now;
int siz[N],son[N];
int id_num[(1<<20)+5];
ll pow2[20];
void dfs(int x,int fa)
{
siz[x]=1;
son[x]=0;
for(int i=0;i<g[x].size();++i)
{
int v=g[x][i];
if(v==fa)
continue;
dfs(v,x);
siz[x]+=siz[v];
if(!son[x]||siz[v]>siz[son[x]])
{
son[x]=v;
}
}
}
//void get_data(int x,int op)
//{
// for(int i=L[x];i<=R[x];++i)
// {
// if(reg[i]==skp)
// {
// i=R[reg[i]];
// continue;
// }
// if(op!=-1)
// {
// int val=a[reg[i]]^op;
// int len=p[val].size();
// for(int j=0;j<len;++j)
// {
// ans+=p[val][j]^reg[i];
// }
// p[a[reg[i]]].push_back(reg[i]);
// }
// else
// {
// p[a[reg[i]]].pop_back();
// }
// }
//}
void cal(int x,int fa,int lca)
{
temp.push_back(x);
for(int i=0;i<20;++i)
{
ans+=1ll*p[a[x]^a[lca]][i][!((x>>i)&1)]*pow2[i];
}
for(int i=0;i<g[x].size();++i)
{
int v=g[x][i];
if(v==fa)
continue;
cal(v,x,lca);
}
}
void del(int x,int fa)
{
if(id_num[a[x]])
{
memset(p[a[x]],0,sizeof(p[a[x]]));
id_num[a[x]]=0;
}
for(int i=0;i<g[x].size();++i)
{
int v=g[x][i];
if(v==fa)
continue;
del(v,x);
}
}
void dsu(int x,int fa,bool keep)
{
//cout<<x<<endl;
for(int i=0;i<g[x].size();++i)
{
int v=g[x][i];
if(v==fa||v==son[x])
continue;
dsu(v,x,0);
}
//cout<<x<<" "<<son[x]<<endl;
if(son[x])
{
dsu(son[x],x,1);
}
for(int i=0;i<20;++i)
p[a[x]][i][(x>>i)&1]++;
id_num[a[x]]++;
//cout<<x<<" "<<g[x].size()<<endl;
for(int i=0;i<g[x].size();++i)
{
int v=g[x][i];
//cout<<v<<" "<<x<<" "<<son[x]<<" "<<fa<<endl;
if(v==fa||v==son[x])
continue;
cal(v,x,x);
for(int j=0;j<temp.size();++j)
{
int it=temp[j];
//int tmp=1;
for(int k=0;k<20;++k)
{
p[a[it]][k][(it>>k)&1]++;
}
id_num[a[it]]++;
}
temp.clear();
}
if(!keep)
{
del(x,fa);
//now=0;
}
}
int main()
{
pow2[0]=1;
for(int i=1;i<20;++i)
pow2[i]=pow2[i-1]<<1;
scanf("%d",&n);
for(int i=1;i<=n;++i)
scanf("%d",&a[i]);
for(int i=1;i<n;++i)
{
int x,y;
scanf("%d%d",&x,&y);
g[x].push_back(y);
g[y].push_back(x);
}
dfs(1,0);
dsu(1,0,1);
printf("%lld\n",ans);
return 0;
}
H. Combination Lock
待補
J. Abstract Painting
狀壓dp,只在x軸上,可以將其兩邊看成是左右擴號,因為圓的半徑最多只有5,所以其左括號最多會對其后十個點產生影響,所以可以用狀壓dp求解,(這里我們將整個圖右移一格)我們設dp[i][j]為以第i個點為右括號對于前10個點狀態為j的方案數(其中1的位置表示其不能為左括號,0表示可以),初始情況,dp[0][j]=0,因為圖右移了一格,所以此數0的位置為負x軸,不能存在左括號,所以方案數為0,對于當前點的每種狀態的dp值,若能由上一個點的dp轉移到,其必須滿足,當前狀態和之前狀態要相應,即之前狀態不能為左括號的位置,當前狀態就不能在那個位置取左括號,(因此之前狀態和當前狀態相與是0才滿足條件),還有因為之前圖上是有圓的,所以還要保證當前狀態得滿足圖上的圓,所以圖上圓的狀態和當前狀態相與得是1,因為如果圖上圓的左括號取到與當前圓的左括號相同位置時,就有兩個交點了,所以要取到當前狀態不能取左括號的地方,因為我們只是列舉了,當前位置為右括號的狀態,所以其實際狀態實際是其最大擴號的狀態或上之前位置的狀態再向左移位一次(因為對于后面的點來說,當前點相切也可以,所以可以取左括號),
#include <bits/stdc++.h>
using namespace std;
int n,k;
int pos[32];
int info[32];
int maxstate=(1<<10)-1;
int dp[1010][(1<<10)];//dp[i][j]代表到第i個位置,[i-9,i]是否被圓包含的二進制狀態為(j)2的方案數
//二進制資訊(j)2的第k位為1,代表點i-k被包含(不能作圓的左括號),反而反之,
vector<int>v[1010];
const int mod=1e9+7;
int main()
{
scanf("%d%d",&n,&k);
for(int i=1;i<=k;++i)
{
int x,r;
scanf("%d%d",&x,&r);
v[x+1+r].push_back(2*r);
}
memset(info,-1,sizeof(info));
for(int i=1;i<32;++i)
{
int tmp=0;
for(int j=4;j>=0;j--)
{
if((i>>j)&1)
{
tmp|=(1<<(j*2+1));
if(info[i]==-1)
{
info[i]=(1<<(j*2+1))-1;
}
}
}
pos[i]=tmp;
}
pos[0]=info[0]=0;
dp[0][maxstate]=1;
for(int i=1;i<=n+1;++i)
{
for(int j=0;j<=maxstate;++j)
{
for(int k=0;k<32;++k)
{
int flag=0;
for(int p=0;p<v[i].size();++p)
{
int r=v[i][p];
if(!(pos[k]&(1<<r-1)))
{
flag=1;
}
}
if(flag||(j&pos[k]))
{
continue;
}
int now=((j|info[k])<<1)&maxstate;
dp[i][now]+=dp[i-1][j];
dp[i][now]%=mod;
}
}
}
int ans=0;
for(int i=0;i<=maxstate;++i)
{
ans+=dp[n+1][i];
ans%=mod;
}
printf("%d\n",ans);
return 0;
}
K. Ragdoll
首先,我們看這個式子 gcd(x,y)=x⊕y,我們要獲得每一個滿足式子的點對,暴力做法是O(n2)的,肯定不行,我們對式子進行調整,兩邊同時異或x,該式子變為 x⊕gcd(x,y)=y,因為是gcd(x,y),所以其一定是x的某個因子,所以我們確定一個值為gcd(x,y),然后對于其每個倍數為x,我們可以找到一個y,再將這些帶到這個式子判斷一下滿不滿足條件即可,這樣就可以O(nlognlongn)的找到所有點對了,然后對于合并,按秩合并即可(總復雜度nlogn),剩下操作暴力完成即可(加點O(1),修改值也是O(1)的因為對于一個值,也就幾十個與其符的點對),
#include <bits/stdc++.h>
using namespace std;
const int N=2e5+5;
const int M=3e5+5;
typedef long long ll;
int gcd(int x,int y)
{
return y==0?x:gcd(y,x%y);
}
vector<int>g[N];
map<int,int>mp[M];
vector<int>s[M];
int fa[M];
int siz[M];
int n,m;
int a[M];
ll ans;
int find(int x)
{
if(x==fa[x])
return x;
else
return fa[x]=find(fa[x]);
}
void add_point(int x,int v)
{
fa[x]=x;
a[x]=v;
s[x].push_back(x);
siz[x]=1;
mp[x][v]=1;
}
void merge(int x,int y)
{
int fa_x=find(x);
int fa_y=find(y);
if(fa_x==fa_y)
return ;
if(siz[fa_x]>siz[fa_y])
swap(fa_x,fa_y);
for(int i=0;i<s[fa_x].size();++i)
{
int x=a[s[fa_x][i]];
for(int j=0;j<g[x].size();++j)
{
int y=g[x][j];
ans+=mp[fa_y][y];
}
}
for(int i=0;i<s[fa_x].size();++i)
{
int x=s[fa_x][i];
s[fa_y].push_back(x);
mp[fa_y][a[x]]++;
}
siz[fa_y]+=siz[fa_x];
fa[fa_x]=fa_y;
}
void update(int x,int v)
{
int fa_x=find(x);
for(int i=0;i<g[a[x]].size();++i)
{
int y=g[a[x]][i];
ans-=mp[fa_x][y];
}
//cout<<ans<<endl;
mp[fa_x][a[x]]--;
a[x]=v;
for(int i=0;i<g[v].size();++i)
{
int y=g[v][i];
ans+=mp[fa_x][y];
//cout<<y<<" "<<mp[fa_x][y]<<endl;
}
mp[fa_x][v]++;
}
int main()
{
for(int i=1;i<=200000;++i)
for(int j=i+i;j<=200000;j+=i)
{
if(gcd(j,i^j)==i)
g[j].push_back(i^j);
}
scanf("%d%d",&n,&m);
for(int i=1;i<=n;++i)
{
scanf("%d",&a[i]);
fa[i]=i;
mp[i][a[i]]=1;
siz[i]=1;
s[i].push_back(i);
}
int t,x,y,v;
while(m--)
{
scanf("%d",&t);
if(t==1)
{
scanf("%d%d",&x,&v);
add_point(x,v);
}
else if(t==2)
{
scanf("%d%d",&x,&y);
merge(x,y);
}
else
{
scanf("%d%d",&x,&v);
update(x,v);
}
printf("%lld\n",ans);
}
return 0;
}
L. Coordinate Paper
構造題,首先,如果我們確定了a1,我們就能確定當前序列的最小情況,即a1,a1+1,a1+2,…,k,0,…0,1,2,…k,0,1…,我們可以O(1)求出其和,這樣我們知道其和%(k+1)是多少,并且如果要修改序列,其%(k+1)的值是不變的,所以,我們斷言如果這個序列能構造出s,其必須滿足,其最小值的和%(k+1)與s%(k+1)是一樣的且s>=其最小值的和,這樣我們可以O(k)的找到a1,找到之后要如何構造呢,就是先對0的位置加(k+1),再對1的位置加(k+1)…即可(試一下就知道其正確性,這樣做是肯定合法的),
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e5+5;
ll n,k,s;
ll ans[N];
struct node
{
ll val;
int id;
}tmp[N];
bool cmp(node a,node b)
{
return a.val<b.val;
}
ll get_ar(ll a)
{
return ((a+1)*a)>>1;
}
ll get_sum(ll a,ll b)
{
ll sum=0;
ll up=k-a+1;
if(b<up)
{
return get_ar(a+b-1)-get_ar(a-1);
}
else
{
sum+=get_ar(k)-get_ar(a-1);
}
ll num=(b-up)/(k+1);
ll num2=(b-up)%(k+1);
sum+=get_ar(k)*num;
sum+=get_ar(num2-1);
return sum;
}
void construct_ans(ll pos)
{
ll num=(s-get_sum(pos,n))/(n*(k+1));
ll num2=(s-get_sum(pos,n))%(n*(k+1));
num2=num2/(k+1);
ans[1]=pos;
tmp[1].id=1;
tmp[1].val=pos;
for(int i=2;i<=n;++i)
{
ans[i]=(ans[i-1]+1)%(k+1);
tmp[i].id=i;
tmp[i].val=ans[i];
}
sort(tmp+1,tmp+1+n,cmp);
for(ll i=1;i<=num2;++i)
{
ans[tmp[i].id]+=(k+1);
}
for(int i=1;i<=n;++i)
{
ans[i]+=num*(k+1);
}
}
int main()
{
scanf("%lld%lld%lld",&n,&k,&s);
int pos;
bool flag=0;
for(int i=0;i<=k;++i)
{
ll a1=i;
if((s%(k+1)==get_sum(a1,n)%(k+1))&&s>=(get_sum(a1,n)))//可以找到解
{
flag=1;
pos=i;
break;
}
}
if(!flag)
puts("-1");
else//構造答案
{
construct_ans(pos);
for(int i=1;i<=n;++i)
printf("%lld ",ans[i]);
puts("");
}
return 0;
}
轉載請註明出處,本文鏈接:https://www.uj5u.com/qita/224861.html
標籤:其他
下一篇:poj1011,我自己的理解
