9.29模拟赛

9.29模拟赛

 

9.29模拟赛

9.29模拟赛

9.29模拟赛

 1 #include<bits/stdc++.h>
 2 #define ll long long
 3 using namespace std;
 4 const ll N=1e6+11;
 5 ll n,m,fa[N],l[N],r[N],seg[N],zh;
 6 bool vis[N];
 7 
 8 inline ll re_ad() {
 9     char ch=getchar(); ll x=0,f=1;
10     while(ch<'0' || ch>'9') { if(ch=='-') f=-1; ch=getchar(); }
11     while('0'<=ch && ch<='9') x=(x<<1)+(x<<3)+ch-'0',ch=getchar();
12     return x*f;
13 }
14 
15 inline ll findfa(ll d) { return fa[d]==d?d:fa[d]=findfa(fa[d]); }
16 
17 inline void Merge(ll p,ll q) {
18     p=findfa(p),q=findfa(q);
19     if(p!=q) fa[p]=q;
20 }
21 
22 int main()
23 {
24     n=re_ad(),m=re_ad();
25     for(ll i=1;i<=n;++i) fa[i]=i;
26     for(ll i=1,x,y;i<=m;++i) {
27         x=l[i]=re_ad(),y=r[i]=re_ad();
28         Merge(x,y);
29         if(x!=y) ++seg[x],++seg[y];
30         else ++zh;
31     }
32     ll lst=findfa(l[1]);
33     for(ll i=2;i<=m;++i) if(findfa(l[i])!=lst) { lst=-1; break; }
34     if(lst==-1) { printf("0\n"); return 0; }
35     ll ans=0;
36     ans+=1ll*zh*(zh-1)/2;
37     ans+=1ll*zh*(m-zh);
38     for(ll i=1;i<=n;++i) ans+=1ll*seg[i]*(seg[i]-1)/2;
39     printf("%lld\n",ans);
40     return 0;
41 }

 9.29模拟赛

9.29模拟赛

9.29模拟赛

 1 #include<bits/stdc++.h>
 2 #define ll long long
 3 using namespace std;
 4 const ll N=111,M=1e7+11;
 5 ll n,k,a[N],sum,p[M],cnt;
 6 
 7 inline ll re_ad() {
 8     char ch=getchar(); ll x=0,f=1;
 9     while(ch<'0' || ch>'9') { if(ch=='-') f=-1; ch=getchar(); }
10     while('0'<=ch && ch<='9') x=(x<<1)+(x<<3)+ch-'0',ch=getchar();
11     return x*f;
12 }
13 
14 int main()
15 {
16     n=re_ad(),k=re_ad();
17     for(ll i=1;i<=n;++i) a[i]=re_ad(),k+=a[i];
18     for(ll i=1;i<=n;++i) for(ll j=1;j*j<=a[i];++j) p[++cnt]=j,p[++cnt]=(a[i]-1)/j+1;
19     sort(p+1,p+cnt+1);
20     cnt=unique(p+1,p+cnt+1)-p-1;
21     ll ans=1;
22     for(ll i=1;i<=cnt;++i) {
23         ll tmp=0;
24         for(ll j=1;j<=n;++j) tmp+=(a[j]-1)/p[i]+1;
25         ll temp=k/tmp;
26         if(temp>=p[i]) ans=temp;
27     }
28     printf("%lld\n",ans);
29     return 0;
30 }

 9.29模拟赛

 

 9.29模拟赛

 

 9.29模拟赛

 

 9.29模拟赛

9.29模拟赛

 

 

 1 #include<bits/stdc++.h>
 2 #define ll long long
 3 using namespace std;
 4 const ll N=1e3+11,inf=1<<29;
 5 ll n,mod,dp[N][N];
 6 int main()
 7 {
 8     scanf("%lld%lld",&n,&mod);
 9     if(n<=1) { printf("0\n"); return 0; }
10     dp[1][0]=dp[1][1]=1;
11     for(ll i=2;i<=n;++i) {
12         ll St=(i<=10)?(1<<i)-1:inf;
13         St=min(St,n-i+2);
14         for(ll l=0;l<=St;++l) for(ll r=0;l+r-1<=St;++r) {
15             ll num=dp[i-1][l]*dp[i-1][r]%mod;
16             (dp[i][l+r+1]+=num)%=mod;
17             (dp[i][l+r]+=num)%=mod;
18             (dp[i][l+r]+=2ll*num*l%mod)%=mod;
19             (dp[i][l+r]+=2ll*num*r%mod)%=mod;
20             (dp[i][l+r-1]+=2ll*num*(l*r%mod)%mod)%=mod;
21             (dp[i][l+r-1]+=num*((l*(l-1)%mod)+(r*(r-1)%mod)))%=mod;
22         }
23     }
24     printf("%lld\n",dp[n][1]);
25     return 0;
26 }
上一篇:关于时间复杂度


下一篇:P1064 [NOIP2006 提高组] 金明的预算方案(DP)