A. Square Counting
思路:
由于题目保证了存在唯一解,因此只要我们能构造出一组解.满足$sum=s$即可.
因为只有一组解.而我们构造的解又符合题意.因此这组解就必定是唯一解.
AC Code：
#include<bits/stdc++.h>
#pragma optimize(2)
#define endl '\n'
#define debug(x) cout<<#x<<":"<<x<<endl;
using namespace std;
typedef long long ll;
typedef pair<int,int>PII;
typedef unsigned long long ull;
const int M=2010;
const ll llinf=0x3f3f3f3f3f3f3f3f;
const int inf=0x3f3f3f3f;
const int mod=1e9+7;
const int N=2e6+10;
int dx[4]={0,1,0,-1};
int dy[4]={-1,0,1,0};
void solve()
{
ll n,s;
cin>>n>>s;
cout<<s/(n*n)<<endl;
return ;
}
int main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
// freopen("test.in","r",stdin);
int t;cin>>t;
while(t--)solve();
return 0;
}
B. Quality vs Quantity
思路:前缀/贪心.
对数据进行一遍排序.最开始的时候.$Red$包含:${a[1],a[2]}$,$Blue$包含：$a[n]$.
为什么这样选? 因为这样选保证了 $Red$的值尽可能小,而$Blue$尽可能多.且满足$Count(Blue)<Count(Red)$:这已经是极限情况了.
因为$Red$再多选一个就无法满足条件了.
因此此后令 $l=2$,$r=n$,两个指针向中间靠近.每次比较下当前这种前缀是否满足条件即可.
AC Code：
#include<bits/stdc++.h>
#pragma optimize(2)
#define endl '\n'
#define debug(x) cout<<#x<<":"<<x<<endl;
using namespace std;
typedef long long ll;
typedef pair<int,int>PII;
typedef unsigned long long ull;
const int M=2010;
const ll llinf=0x3f3f3f3f3f3f3f3f;
const int inf=0x3f3f3f3f;
const int mod=1e9+7;
const int N=2e6+10;
int dx[4]={0,1,0,-1};
int dy[4]={-1,0,1,0};
ll s[N];
void solve()
{
int n;cin>>n;
vector<ll>a(n+1);
for(int i=1;i<=n;i++)cin>>a[i];
sort(a.begin()+1,a.end());
for(int i=1;i<=n;i++)s[i]=s[i-1]+a[i];
int l=2,r=n;
while(l<r)
{
ll res1=s[l],res2=s[n]-s[r-1];
if(res2>res1)
{
cout<<"YES"<<endl;
return;
}else l++,r--;
}
cout<<"NO"<<endl;
return ;
}
int main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
// freopen("test.in","r",stdin);
int t;cin>>t;
while(t--)solve();
return 0;
}
C. Factorials and Powers of Two
思路:
状态压缩/按位压缩/枚举/思维
这样的数一共大约有 65个
首先如果暴力的枚举所有,题目定义的数的可能和.
需要的空间复杂度为:$C_{65}^{1} + C_{65}^{2}+.....+C_{65}^{65} = 2^{65}$
空间复杂度是$2^{65}$肯定爆内存.
因此需要思考一下....
由于$2^{x}$是满足条件的数.因此实际上将任意$n$分解成二进制的时候.计算一下有多少位为1就行.
因此 无论如何都存在方案.
考虑如何优化,由于阶乘比较少 只有15个.我们考虑去枚举所有阶乘的和,也就是$2^{15} = 23768$.这里阶乘的方案用set保存方便去重
因此正解就是 枚举所有可能用到的阶乘和.剩下的数只需要计算下 二进制有几个1即可.
AC Code：
#include<bits/stdc++.h>
#pragma optimize(2)
#define endl '\n'
#define debug(x) cout<<#x<<":"<<x<<endl;
using namespace std;
typedef long long ll;
typedef pair<int,int>PII;
typedef unsigned long long ull;
const int M=2010;
const ll llinf=0x3f3f3f3f3f3f3f3f;
const int inf=0x3f3f3f3f;
const int mod=1e9+7;
const int N=2e6+10;
int dx[4]={0,1,0,-1};
int dy[4]={-1,0,1,0};
ll fac[20];
struct node{
int cnt;ll val;
bool operator <(const node &a)const
{
return val<a.val;
}
};
set<node>st;//保存所有的方案
void solve()
{
ll n;cin>>n;
ll ans=0;
for(int i=0;i<50;i++)
if((n>>i)&1)ans++;//先统计出最劣的方案
for(set<node>::iterator it=st.begin();it!=st.end();++it)
{
if(it->val<=n)//方案是可执行的
{
ll tmp=n-it->val;
ll cur=it->cnt;
for(int j=0;j<50;j++)
if((tmp>>j)&1)cur++;
ans=min(ans,cur);
}
}
cout<<ans<<endl;
return ;
}
ll res=(1<<16)-1;
int main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
// freopen("test.in","r",stdin);
for(int i=0;i<=15;i++)
{
fac[i]=1;
for(int j=1;j<=i;j++)fac[i]=fac[i]*j;
}//预处理出阶乘
// for(int i=0;i<=15;i++)cout<<i<<' '<<fac[i]<<endl;
for(int i=0;i<=res;i++)
{
ll tmp=0;
int cnt=0;
for(int j=0;j<15;j++)
if((i>>j)&1)tmp+=fac[j+1],cnt++;
st.insert({cnt,tmp});
}
int t;cin>>t;
while(t--)solve();
return 0;
}
D. Weight the Tree
思路:
树形Dp
当 $n=2$时,此时两个点都是$good$.也可以满足条件.
当 $n>2$时,首先证明,对于任意相邻的两个点.只要其中一个被选中为$good$,另一个一定不是$good$.
反证法:
假设此时两个点都是 $good$,若二者点权不等.显然此时两个点就不可能同时是另一个点和其他点的和.
若两者点权相等,则由于若此时还存在任何其他和这两个点中一个相连的点都会增加其中一个的点权,进而使得
其中一点,点权从$w[u]=w[v]$变成$w[v]=w[u]+x$.显然此时无论 $w[u]$变成多少二者都不会相等
因此若存在,相邻两个$good$此时两点不能和任何其其他点相连,情况就退化成了第一种情况.
因此得到结论,$n>2$时,相邻点不能同时为$good$.
此时我们还需要构造一种方式使得,我们构造出的树的点权最小.
我们可以将树中的点 分为两类: $good$ 以及$ungood$.
点权之和:
$sum=sum_{good}+sum_{ungood}$.
我们知道,$good$的点权是和其相邻的点权之和.
而$good$又不能和$good$相邻,
因此$good$的相邻的点,就是$ungood$.因此$sum$实际上只受,$ungood$的影响.
那么我们只要把所有$ungood$赋值成1
这样构造出来的树的点权就一定是最小的了.
至于如何构造出尽可能多的 $good$用树形Dp就行了.
动态规划,需要同时维护两个信息:$sum$和$num$.因为我们要在保证$num$尽可能大的情况下缩点权.
以根节点为例子
状态定义:$F[u][0]/F[u][1]$$(w,num)$ 以$u$为根节点的子树,在保证$good$点尽可能最大的情况下,的最小点权.
状态转移就是:
$f[root][0].num + =f[child][0].num,f[root][0].w + =min(f[child][0].w,f[child][1].w); $
$f[root][1].w + =f[child][0].w,f[root][1].num + =f[child][0].num; $
*重点：每次转移的时候对于$0$状态而言都需要讨论一下,究竟他的哪一个子节点的$num$更大
因为我们是在$num$尽可能大的情况下,缩小权值.否则可能权值缩小了,但$num$不一定是最大.
因此对于$0$状态,一定是从$num$最大的$child$转移而来.
AC Code:
#include<bits/stdc++.h>
#pragma optimize(2)
#define endl '\n'
#define debug(x) cout<<#x<<":"<<x<<endl;
using namespace std;
typedef long long ll;
typedef pair<int,int>PII;
typedef unsigned long long ull;
const int M=2010;
const ll llinf=0x3f3f3f3f3f3f3f3f;
const int inf=0x3f3f3f3f;
const int mod=1e9+7;
const int N=2e6+10;
int dx[4]={0,1,0,-1};
int dy[4]={-1,0,1,0};
int n;
int e[N],ne[N],h[N],idx;
void add(int a,int b)
{
e[idx]=b,ne[idx]=h[a],h[a]=idx++;
}
struct node{
ll w;int num;
};
node f[N][2];
ll d[N];
void dp(int u,int fa)
{
f[u][0].w=1;
f[u][1].w=d[u],f[u][1].num=1;//子树是不包含父节点的
for(int i=h[u];~i;i=ne[i])
{
int j=e[i];
if(j!=fa)
{
dp(j,u);
/* if(u==1)
{
cout<<u<<' '<<j<<endl;
cout<<f[u][0].w<<' '<<f[j][0].w<<' '<<f[j][1].w<<endl;
} */
if(f[j][0].num>f[j][1].num)
{
f[u][0].w+=f[j][0].w;
f[u][0].num+=f[j][0].num;
}else if(f[j][0].num<f[j][1].num)
{
f[u][0].w+=f[j][1].w;
f[u][0].num+=f[j][1].num;
}else
{
f[u][0].num+=f[j][0].num;
f[u][0].w+=min(f[j][0].w,f[j][1].w);
}//按值讨论一遍
f[u][1].w+=f[j][0].w,f[u][1].num+=f[j][0].num;
}
}
}
int ans[N];
void dfs(int u,int fa,int state)
{
int cur;
if(state==0)
{
if(f[u][0].num>f[u][1].num)
{
ans[u]=1;
cur=0;
}else if(f[u][0].num<f[u][1].num)ans[u]=d[u],cur=1;
else
{
if(f[u][0].w<=f[u][1].w)ans[u]=1,cur=0;
else ans[u]=d[u],cur=1;
}
}else ans[u]=1,cur=0;
// cout<<u<<' '<<cur<<endl;
for(int i=h[u];~i;i=ne[i])
{
int j=e[i];
if(j!=fa)
{
dfs(j,u,cur);
}
}
}
void solve()
{
memset(h,-1,sizeof h);
cin>>n;
if(n==2)
{
cout<<2<<' '<<2<<endl;
cout<<1<<' '<<1<<endl;
return;
}
for(int i=1;i<=n-1;i++)
{
int a,b;
cin>>a>>b;
add(a,b);
add(b,a);
d[b]++,d[a]++;
}
dp(1,-1);
if(f[1][1].num>f[1][0].num)
{
cout<<f[1][1].num<<' '<<f[1][1].w<<endl;
dfs(1,-1,0);
}
else if(f[1][1].num<f[1][0].num)
{
cout<<f[1][0].num<<' '<<f[1][0].w<<endl;
dfs(1,-1,1);
}
else
{
if(f[1][1].w<=f[1][0].w)
{
cout<<f[1][1].num<<' '<<f[1][1].w<<endl;
dfs(1,-1,0);
}
else if(f[1][1].w>f[1][0].w)
{
cout<<f[1][0].num<<' '<<f[1][0].w<<endl;
dfs(1,-1,1);
}
}
for(int i=1;i<=n;i++)cout<<ans[i]<<' ';
cout<<endl;
/* cout<<endl;
cout<<f[8][0].w<<endl;
cout<<f[6][0].w<<' '<<f[3][0].w<<endl;*/
}
int main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
// freopen("test.in","r",stdin);
solve();
return 0;
}
E. Power Board
AC Code:
#include<bits/stdc++.h>
#pragma optimize(2)
#define endl '\n'
#define debug(x) cout<<#x<<":"<<x<<endl;
using namespace std;
typedef long long ll;
typedef pair<int,int>PII;
typedef unsigned long long ull;
const int M=2010;
const ll llinf=0x3f3f3f3f3f3f3f3f;
const int inf=0x3f3f3f3f;
const int mod=1e9+7;
const int N=2e7+10;
int dx[4]={0,1,0,-1};
int dy[4]={-1,0,1,0};
//n*m-(min(n,m)*min(n,m)-min(n,m))/2
bool vis[N];
bool mp[N];
//unordered_map<int,bool>vis;
//unordered_map<int,bool>mp;
int cow[30];//记录下表格i*m行有多少个不同的数字
ll qpow(ll a,ll b)
{
ll res=1;
while(b)
{
if(b&1)res=res*a;
a=a*a;
b>>=1;
}
return res;
}
void solve()
{
// cout<<qpow(2,4)<<endl;
int n,m;
cin>>n>>m;
// cout<<n<<' '<<m<<endl;
int cnt=0;
for(int i=1;i<=20;i++)
{
for(int j=1;j<=m;j++)
{
int x=i*j;
if(!mp[x])mp[x]=true,cnt++;
}
cow[i]=cnt;
}
// for
ll ans=1;
for(int i=2;i<=n;i++)//从第二行开始
{
if(!vis[i])
{
int res=1;
while(qpow(i,res)<=n)vis[qpow(i,res)]=true,res++;//计算出列表的行号
//n*m-(min(n,m)*min(n,m)-min(n,m))/2 计算公式
if(qpow(i,res)>n)res--;
ans+=cow[res];//
}
}
cout<<ans<<endl;
return ;
}
int main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
// freopen("test.in","r",stdin);
solve();
return 0;
}
