震惊，全机房都 (mathbb{AK}) 了，就我没有。
T1: 100 ( ightarrow) 90
T1:容易题
震惊，减法居然还要取模。事实上看起来更大的数由于模之后可能变小，导致减一个看起来更小的数也会爆负数。
好像大家都秒切这道题了。记录一下我的思路：
有一个数据点是 (k=0)，是一个很好的提示。我们发现，(k=0) 的时候答案显然是 (Big(cfrac{n(n+1)}{2}Big)^m)（简单的乘法分配率）。那么我们考虑有修改的时候，大多就是把这些 (cfrac{n(n+1)}{2}) 减去了一些数，再乘起来。我们看到 (n) 很大，但 (k) 并不大。我们并不关心数排列的顺序，所以我们可以直接离散化就行了。修改的单独乘，最后乘上 (Big(cfrac{n(n+1)}{2}Big)^{m-cnt}) 即可。
注意输入数据中有重复的，可以用 map 去重。
Code
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int Mod=1e9+7;
const int maxn=1e5+10;
int n,m,K;
inline int read(){
int x=0;bool fopt=1;char ch=getchar();
for(;!isdigit(ch);ch=getchar())if(ch=='-')fopt=0;
for(;isdigit(ch);ch=getchar())x=(x<<3)+(x<<1)+ch-48;
return fopt?x:-x;
}
inline int qpow(int x,int b){
int ans=1,base=x;
while(b){
if(b&1)ans=ans*base%Mod;
base=base*base%Mod;
b>>=1;
}
return ans;
}
int a[maxn];
int cnt;
map<int,int> mp;
map<pair<int,int>,bool> vis;
signed main(){
#ifndef LOCAL
freopen("easy.in","r",stdin);
freopen("easy.out","w",stdout);
#endif
n=read();m=read();K=read();
for(int i=1;i<=K;i++){
a[i]=n*(n+1)%Mod*qpow(2,Mod-2)%Mod;
}
for(int i=1;i<=K;i++){
int x=read(),y=read();
pair<int,int> temp;
temp.first=x;temp.second=y;
if(vis[temp])continue;
else vis[temp]=1;
if(!mp[x]){
mp[x]=++cnt;
}
a[mp[x]]=(a[mp[x]]-y+Mod)%Mod;//减法不模见祖宗
}
int res=1;
for(int i=1;i<=cnt;i++){
res=res*a[i]%Mod;
}
res=res*qpow(n*(n+1)%Mod*qpow(2,Mod-2)%Mod,m-cnt)%Mod;
printf("%lld
",res);
return 0;
}
T2:兔子与樱花
震惊，今天第二次把贪心题当 (DP) 做，人傻了。
另外大家一定要自信，万一有 (O(ncdot 2^n)) 的数据呢，结果就真的有 20 分。
实际上是道**贪心题。然而我们需要枚举删哪个儿子，而不是像我这个**一样判断删不删父亲（这波啊，这波是弑父）。显然我们优先删代价小的儿子最优。直接 sort 就完了。当删不了了直接 break 掉。
Code
#include <bits/stdc++.h>
using namespace std;
const int maxn=2e6+10;
int n,m,ans;
int c[maxn],son[maxn];
struct Edge{
int from,to,nxt;
}e[maxn];
inline int read(){
int x=0;bool fopt=1;char ch=getchar();
for(;!isdigit(ch);ch=getchar())if(ch=='-')fopt=0;
for(;isdigit(ch);ch=getchar())x=(x<<3)+(x<<1)+ch-48;
return fopt?x:-x;
}
int head[maxn],cnt;
inline void add(int u,int v){
e[++cnt].from=u;
e[cnt].to=v;
e[cnt].nxt=head[u];
head[u]=cnt;
}
int a[maxn];
void dfs(int u){
for(int i=head[u];i;i=e[i].nxt)
dfs(e[i].to);
int tot=0;
for(int i=head[u];i;i=e[i].nxt)
a[++tot]=c[e[i].to];
sort(a+1,a+tot+1);
for(int i=1;i<=tot;i++){
if(c[u]+a[i]-1<=m){
ans++;
c[u]+=a[i]-1;
}else break;
}
}
int main(){
#ifndef LOCAL
freopen("rabbit.in","r",stdin);
freopen("rabbit.out","w",stdout);
#endif
n=read();m=read();
for(int i=1;i<=n;i++)
c[i]=read();
for(int i=1;i<=n;i++){
son[i]=read();
c[i]+=son[i];
for(int j=1;j<=son[i];j++){
int v=read()+1;
add(i,v);
}
}
dfs(1);
printf("%d
",ans);
return 0;
}