Codeforces Round #202 (Div. 1)
首先肯定是先找到最大的ai为maxx 答案起码是maxx
发现如果我们按照从大到小依次摆放 只要maxx*(n-1)能容下Σai 那一定能满足(自行模拟一下就好，顺序一定是从大到小)
所以我们只要不断使maxx++ 直到maxx*(n-1)>=Σai就好
#include
using namespace std;
#define lowbit(x) x&(-x)
#define ll long long
const int maxn=1e5+5;
ll n,ans;
ll tot,a[maxn];
int main(){
cin>>n;
for(int i=1;i<=n;i++)cin>>a[i],tot+=a[i],ans=max(a[i],ans);
while(1){
if(ans*(n-1)>=tot){
cout< 
这个题看似很简单 确实可以很简单 但是确实也可以难倒人 我就是
开始我的思路一直是从下往上走 却发现根本行不通 索性换个思路 从上往下
假设整棵树的苹果总数为x，我们假设根节点有n棵子树，那么分给每棵子树的苹果数为x/n，并且x一定是n的倍数
利用递归，将子树的苹果平均分给子树的子树。。。
一直到叶子节点，此时我们可以知道，该叶子节点分到的苹果为x的k分之一，因此x为k的倍数，并且x/k不大于该叶子的原来的苹果数
根据这个，我们可以得到一个最小的x; 但要保证x能够均分给每个子树 怎么办？减去 x%所有的lcm 就好
另外，为了避免倍数累乘的时候溢出，当发现k>x时，易知只能将所有的苹果都移掉，直接输出即可。
#include
#include
#include
#include
using namespace std;
#define MAXN 100010
typedef long long ll;
int n;
int num[MAXN];
vector G[MAXN];
ll x,sum=0,lcm=1;
ll gcd(ll a,ll b)
{
return b==0 ? a : gcd(b, a%b);
}
void dfs(int cur=1, ll div=1LL, int fa=-1)
{
if(div>x)
{
cout<>n;
for(int i=1; i<=n; i++)
{
scanf("%d", &num[i]);
sum+=(ll)num[i];
}
x=sum;
for(int i=1; i<=n-1; i++)
{
int u,v;
scanf("%d %d", &u, &v);
G[u].push_back(v);
G[v].push_back(u);
}
dfs();
cout< 
题目还是很好明白 但是思来想去就是想不明白用什么数据结构维护
这个题目思路特别好
为什么要考虑分块？首先想不到合适的数据结构只有暴力
现在有两个问题
1.考虑该集合对其他集合造成的影响
2.该集合当前的Σ是多少
分块的好处在于 考虑 大集合：集合大小 > √集合总数 的集合个数 < √集合总数
小集合：集合大小 < √集合总数 的集合大小 < √集合总数
这样我们分别对 大集合进行操作1 和 小集合进行操作2 时间复杂度就能保证
不得不说这个题目思路真的好牛
//Subset Sums
#include
#include
#include
#include
#include
using namespace std;
typedef long long lint;
inline int read()
{
int x=0,f=1; char ch=getchar();
while(ch<'0'||'9' x;} s[N];
bool cmpSiz(_set x,_set y) {return x.siz>y.siz;}
bool tmp[N]; int cnt[N0][N]; lint add[N0],sum[N0];
int main()
{
n=read(),m=read(),q=read();
for(int i=1;i<=n;i++) a[i]=read();
int sumK=0;
for(int i=1;i<=m;i++)
{
s[i].siz=read(),s[i].id=i,s[i].x.push_back(0); sumK+=s[i].siz;
for(int p=1;p<=s[i].siz;p++) s[i].x.push_back(read());
}
sort(s+1,s+m+1,cmpSiz);
for(int i=1;i<=m;i++) ori[s[i].id]=i;
n0=sqrt(sumK); int cnt1=0;
for(int i=1;s[i].siz>=n0;i++) cnt1=i;
for(int i=1;i<=cnt1;i++)
{
memset(tmp,false,sizeof tmp);
for(int p=1;p<=s[i].siz;p++) sum[i]+=a[s[i].x[p]],tmp[s[i].x[p]]=true;
for(int j=1;j<=m;j++)
for(int p=1;p<=s[j].siz;p++) if(tmp[s[j].x[p]]) cnt[i][j]++;
}
for(int owo=1;owo<=q;owo++)
{
char opt; scanf("%c",&opt);
if(opt=='?')
{
int k=ori[read()];
if(k<=cnt1) printf("%lld\n",sum[k]);
else
{
lint res=0;
for(int p=1;p<=s[k].siz;p++) res+=a[s[k].x[p]];
for(int i=1;i<=cnt1;i++) res+=add[i]*cnt[i][k];
printf("%lld\n",res);
}
}
if(opt=='+')
{
int k=ori[read()]; lint v=read();
if(k<=cnt1) add[k]+=v;
else for(int p=1;p<=s[k].siz;p++) a[s[k].x[p]]+=v;
for(int i=1;i<=cnt1;i++) sum[i]+=v*cnt[i][k];
}
}
return 0;
}
经典的LGV定理 考虑起点为 (1,2)和(2,1) 终点为(n-1,m) 和 (n,m-1)
最后大数据读入要用scanf 我用cin超时了！！！！
#include
using namespace std;
#define lowbit(x) x&(-x)
#define ll long long
const int maxn=3e3+5;
const int mod=1e9+7;
int n,m;
ll dp[maxn][maxn][2];
char c[maxn][maxn];
int main(){
cin>>n>>m;
dp[2][1][0]=dp[1][2][1]=1;
for(int i=1;i<=n;i++)
scanf("%s",c[i]+1);
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++){
if(c[i][j]=='#')continue;
if(c[i][j-1]=='.'){
dp[i][j][0]=(dp[i][j][0]+dp[i][j-1][0])%mod;
if(j-1>=2)
dp[i][j][1]=(dp[i][j][1]+dp[i][j-1][1])%mod;
}
if(c[i-1][j]=='.'){
dp[i][j][1]=(dp[i][j][1]+dp[i-1][j][1])%mod;
if(i-1>=2)
dp[i][j][0]=(dp[i][j][0]+dp[i-1][j][0])%mod;
}
}
cout<<(dp[n][m-1][0]*dp[n-1][m][1]%mod+mod-dp[n-1][m][0]*dp[n][m-1][1]%mod)%mod<