G - 區間權值
題目描述
小 Bo 有 n 個正整數 a1..an，以及一個權值序列 w1…wn，現在他定義
現在他想知道
的值，需要你來幫幫他
你隻需要輸出答案對 109+7 取模後的值
輸入描述:
第一行一個正整數 n
第二行 n 個正整數 a1..an
第三行 n 個正整數 w1..wn
輸出描述:
輸出答案對 109+7 取模後的值
示例1
輸入
複制
3
1 1 1
1 1 1
輸出
複制
10
備注:
1≤ n≤ 3x 105
1≤ ai≤ 107
1≤ wi≤ 107
注意：取模的時候不要ans+=balabala%mod，這樣隻是給等号後的數取模了，沒有給ans加後的值取模，會爆的嘤嘤嘤qwq
代碼如下：
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<string>
#include<cstring>
#include<queue>
#include<cmath>
#include<set>
#define ll long long
using namespace std;
const int N=300005,mod=1e9+7;
ll sumA[N],sumB1[N],sumB[N],W[N],a[N];
int main(){
int n;
scanf("%d",&n);
memset(sumA,0,sizeof(sumA));
memset(sumB,0,sizeof(sumB));
memset(sumB1,0,sizeof(sumB1));
for(int i=1;i<=n;i++){
scanf("%lld",&a[i]);
sumA[i]=(sumA[i-1]+a[i])%mod;
}
for(int i=1;i<=n;i++){
sumB[i]=(a[i]*i%mod+sumB[i-1])%mod;
sumB1[i]=(a[n-i+1]*i%mod+sumB1[i-1])%mod;
}
for(int i=1;i<=n;i++){
scanf("%lld",&W[i]);
}
ll tmp,ans;
int k;
if(n==1)ans=W[1]*a[1];
else ans=(sumA[n]*W[1]%mod+sumA[n]*W[n]%mod)%mod;
for(int r=2;r<n;r++){
if(2*r-1<=n)k=r;
else{
k=min(r-1,n-r+1);
}
tmp=((sumB[k-1]+sumB1[k-1])%mod+((sumA[n-k+1]-sumA[k-1])+mod)%mod*k%mod)%mod;
ans=(ans+tmp*W[r]%mod)%mod;
}
printf("%lld\n",ans);
}
I - 連通塊計數
題目描述
小 A 有一棵長的很奇怪的樹，他由 n 條鍊和 1 個點作為根構成，第 i 條鍊有 ai 個點，每一條鍊的一端都與根結點相連。
現在小 A 想知道，這棵長得奇怪的樹有多少非空的連通子樹，你隻需要輸出答案對 998244353 取模的值即可
輸入描述:
第一行一個正整數 n
第二行 n 個正整數 a1…an
輸出描述:
輸出答案對 998244353 取模後的值
示例1
輸入
複制
2
1 1
輸出
複制
6
備注:
1≤ n≤ 105
1≤ ai≤ 107
思路：這是個思維題啊，還挺不錯的
當沒有根的時候：bi=(a[i]+1)*a[i]/2 把b1到bn加起來
當有根的時候(a[1]+1)*(a[2]+1)*…(a[n]+1)
不考慮根的情況好了解，當有根節點的時候，每一條鍊從根開始，一共有1,2,3…1+a[i]種情況，把每個鍊的情況乘起來就好啦~
代碼如下：
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<string>
#include<cstring>
#include<queue>
#include<cmath>
#include<set>
#define ll long long
using namespace std;
const int N=300005,mod=998244353;
ll mod_pow(ll a,ll b){
ll res=1;
while(b){
if(b&1)res=res*a%mod;
a=a*a%mod;
b>>=1;
}
return res;
}
int main(){
int n;
ll a;
scanf("%d",&n);
ll res1=1,res2=0;
for(int i=1;i<=n;i++){
scanf("%lld",&a);
res2=(res2+a*(a+1)%mod*mod_pow(2,mod-2))%mod;
res1=res1*(a+1)%mod;
}
printf("%lld\n",(res1+res2)%mod);
}
H - 樹鍊博弈
題目描述
給定一棵 n 個點的樹，其中 1 号結點是根，每個結點要麼是黑色要麼是白色
現在小 Bo 和小 Biao 要進行博弈，他們兩輪流操作，每次選擇一個黑色的結點将它變白，之後可以選擇任意多個(可以不選)該點的祖先(不包含自己)，然後将這些點的顔色翻轉，不能進行操作的人輸
由于小 Bo 猜拳經常輸給小 Biao，他想在這個遊戲上扳回一城，現在他想問你給定了一個初始局面，是先手必勝還是後手必勝
輸入描述:
第一行一個正整數 n
第二行 n 個整數 w1..wn，wi∈ {0,1}，wi=1 表示第 i 個結點一開始是黑點，否則是白點
接下來 n-1 行，每行兩個正整數 u,v 表示一條樹邊 (u,v)
輸出描述:
如果先手必勝，輸出First ，否則輸出Second
示例1
輸入
複制
2
1 0
1 2
輸出
複制
First
備注:
1≤ n≤ 1000
思路：
（1）若每層的黑點數都為偶數那麼先手必敗，因為先手改一層的黑點為白點，然後操作完，後手改相同層的黑點為白點，然後做和先手相同的操作，那麼祖先相當于沒變，每層都是偶數那麼一定能保證先手到無路可走的狀态。
（2）反之，先手勝，先手先把深度最大的奇數層的變為偶數，然後對其祖先操作，使得每層的黑點數都是偶數，接着後手操作，先手做（1）操作，後手敗。
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<string>
#include<cstring>
#include<queue>
#include<cmath>
#include<set>
#define ll long long
using namespace std;
const int N=1005,mod=998244353;
int a[N];
struct pro{int from,to,next;};
pro edge[2*N];
int cnt=0,head[N],depth[N];
void addEdge(int from,int to){
edge[cnt].from=from;
edge[cnt].to=to;
edge[cnt].next=head[from];
head[from]=cnt++;
}
void dfs(int pre,int now,int dep){
depth[dep]+=a[now];
for(int i=head[now];i!=-1;i=edge[i].next){
int v=edge[i].to;
if(v==pre)continue;
dfs(now,v,dep+1);
}
}
int main(){
int n;
scanf("%d",&n);
memset(head,-1,sizeof(head));
memset(depth,0,sizeof(depth));
for(int i=1;i<=n;i++){
scanf("%d",&a[i]);
}
int s,t;
for(int i=1;i<n;i++){
scanf("%d%d",&s,&t);
addEdge(s,t);
addEdge(t,s);
}
dfs(0,1,1);
int ans=0;
for(int i=1;i<=n;i++)if(depth[i]%2==1)ans=1;
if(ans)printf("First\n");
else printf("Second\n");
}
判斷的時候
if(depth[i]%2==1){ans=1;break;}
加個break就隻能過70%不知道為什麼