D
预处理勾股数然后暴力判断是否满足条件
#include <bits/stdc++.h>
using namespace std;
int i,j,k,n,m,x,y,t,p,q,T;
vector<pair<int,int> >b[10000010];
int gcd(int x,int y){
return y==0?x:gcd(y,x%y);
}
int main(){
for (i=1;i<=3300;i++)
for (j=i;j<=3300;j++)
if (i*i+j*j<=10000000){
b[i*i+j*j].push_back(make_pair(i,j));
}
scanf("%d",&T);
while (T--){
scanf("%d%d",&p,&q);
x=gcd(p,q);p/=x;q/=x;
int flag=0;
for (i=0;i<b[p].size();i++){
x=b[p][i].first;y=b[p][i].second;
if (x*y==q){
printf("%d %d\n",x,y);
flag=1;break;
}
}
if (flag==1)continue;
printf("0 0\n");
}
}
E
简单的二分DP
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+5;
int n,k,a[N],b[N],f[N];
int main()
{
//srand(time(0));
//freopen("1.in","r",stdin);
//freopen("1.out","w",stdout);
//int T; cin>>T; while(T--) work();
cin>>n>>k;
for(int i=1;i<=n;i++)scanf("%d",&a[i]);
sort(a+1,a+1+n);
for (int i=1;i<=n;i++){
int l=1,r=i-1,ans=0;
while (l<=r){
int mid=l+r>>1;
if (a[mid]<=a[i]-k)ans=mid,l=mid+1;else r=mid-1;
}
f[i]=f[ans]+1;
}
printf("%d\n",f[n]);
return 0;
}
G
树形DP
一开始想复杂了
对于一个子树中是否有边要往上连其实是确定的。。。
#include <cstdio>
using namespace std;
const int N=100010;
const int mod=998244353;
int fi[200010],ne[200010],la[200010],a[200010];
int i,j,k,n,m,x,y,t;
int f[100010],fac[100010];
void add(int x,int y){
k++;a[k]=y;
if (fi[x]==0)fi[x]=k;else ne[la[x]]=k;
la[x]=k;
}
int dfs(int x,int fa){
int cnt=0;f[x]=1;
for (int i=fi[x];i;i=ne[i])
if (a[i]!=fa){
cnt+=dfs(a[i],x);
f[x]=1ll*f[x]*f[a[i]]%mod;
}
if (cnt&1){
f[x]=1ll*cnt*fac[cnt-1]%mod*f[x]%mod;
}
else f[x]=1ll*f[x]*fac[cnt]%mod;
return cnt+1&1;
}
int main(){
scanf("%d",&n);
for (i=1;i<n;i++){
scanf("%d%d",&x,&y);
add(x,y);add(y,x);
}
fac[0]=1;
for (i=1;i<=n;i++)
if (i&1)
fac[i]=1ll*fac[i-1]*i%mod;
else fac[i]=fac[i-1];
dfs(1,-1);
printf("%d\n",f[1]);
return 0;
}H
Kruscal合并边时建一个新点，边权为E-两棵子树权值和
然后倍增
#include <bits/stdc++.h>
using namespace std;
const int N=200010;
struct edge{
int x,y,t;
}e[N];
int i,j,k,n,m,x,y,t,q,a[N],fa[N],size[N];
int f[N][19],g[N][19];
bool cmp(const edge&a,const edge &b){
return a.t<b.t;
}
int find(int x){
return fa[x]==x?x:fa[x]=find(fa[x]);
}
void add(int x,int y,int t){
f[x][0]=y;g[x][0]=t;
}
int main(){
// freopen("1.in","r",stdin);
// freopen("1.out","w",stdout);
scanf("%d%d%d",&n,&m,&q);
for (i=1;i<=n;i++)scanf("%d",&a[i]);
for (i=1;i<=n;i++)fa[i]=i,size[i]=a[i];
for (i=1;i<=m;i++){
scanf("%d%d%d",&x,&y,&t);
e[i]={x,y,t};
}
sort(e+1,e+1+m,cmp);int nn=n;
for (i=1;i<=m;i++){
x=e[i].x;y=e[i].y;
if (find(x)==find(y))continue;
int u=find(x),v=find(y);
nn++;fa[nn]=nn;size[nn]=size[v]+size[u];
add(u,nn,e[i].t-size[u]);add(v,nn,e[i].t-size[v]);
fa[u]=nn;fa[v]=nn;
}
g[nn][0]=1100000000;
for (k=1;k<=18;k++)
for (i=1;i<=nn;i++)
f[i][k]=f[f[i][k-1]][k-1];
for (k=1;k<=18;k++)
for (i=1;i<=nn;i++)
g[i][k]=max(g[i][k-1],g[f[i][k-1]][k-1]);
while (q--){
scanf("%d%d",&x,&t);
for (k=18;k>=0;k--)
if (g[x][k]<=t){
x=f[x][k];
}
printf("%d\n",size[x]+t);
}
return 0;
}
I
普普通通的背包DP。。。
#include <bits/stdc++.h>
using namespace std;
long long f[2][110][2610];
int v[110],t[110];
int i,j,k,n,m,x,y,K;
int main(){
scanf("%d%d",&n,&K);
for (i=1;i<=n;i++){
scanf("%d%d",&v[i],&t[i]);
}
for (i=0;i<=K;i++)for (j=0;j<=2600;j++)f[0][i][j]=-1ll<<60;
f[0][0][1300]=0;
for (i=1;i<=n;i++){
for (j=0;j<=K;j++)
for (k=0;k<=2600;k++)f[i%2][j][k]=f[(i-1)%2][j][k];
for (j=0;j<=K;j++)
for (k=t[i];k<=2600;k++)
f[i%2][j][k]=max(f[i%2][j][k],f[(i-1)%2][j][k-t[i]]+v[i]);
for (j=1;j<=K;j++)
for (k=2*t[i];k<=2600;k++)
f[i%2][j][k]=max(f[i%2][j][k],f[(i-1)%2][j-1][k-2*t[i]]+v[i]);
for (j=0;j<=K;j++)
for (k=0;k<=2600-t[i];k++)
f[i%2][j][k]=max(f[i%2][j][k],f[(i-1)%2][j][k+t[i]]+v[i]);
for (j=1;j<=K;j++)
for (k=0;k<=2600-2*t[i];k++)
f[i%2][j][k]=max(f[i%2][j][k],f[(i-1)%2][j-1][k+2*t[i]]+v[i]);
}
long long ans=0;
for (i=0;i<=K;i++)ans=max(ans,f[n%2][i][1300]);
printf("%lld\n",ans);
return 0;
}
J
BITSET求出每一位的K值然后AND起来
#include <unordered_map>
#include <cstdio>
#include <bitset>
#include <algorithm>
using namespace std;
int a[50010],s[50010],b[50010];
bitset<50001>B[50010],ans,yi;
int i,j,k,n,m,x,y,t,num,T;
unordered_map<int,int> mp;
char ch;
void print(bitset<50001> b){
for (int i=1;i<=n;i++)printf("%d",(int)b[i]);printf("\n");
}
int main(){
scanf("%d",&T);
while (T--){
mp.clear();mp[0]=0;
scanf("%d\n",&n);
for (i=1;i<=n;i++)yi[i]=1;ans=yi;
for (i=1;i<=n;i++){
scanf("%c",&ch);
s[i]=s[i-1]+ch-'0';
}
for (i=1;i<=n;i++)s[i]=2*s[i]-i;
scanf("\n");
for (i=1;i<=n;i++){
scanf("%c",&ch);
b[i]=ch-'0';
}
for (i=1;i<=n;i++){
B[i].reset();
if (mp.find(s[i])==mp.end()){
if (s[i]>s[i-1])B[i]=yi;
}
else{
x=mp[s[i]];
if (s[i]==s[i-1]+1){
B[i]=(B[x]<<(i-x))|(yi>>(n-(i-x)));
}
else B[i]=B[x]<<(i-x);
B[i][i-x]=0;
}
// printf("=====\n");
// print(ans);
if (b[i]==0)ans&=yi^B[i];else ans&=B[i];
// print(B[i]);
// print(ans);
// printf("=====\n");
mp[s[i]]=i;
}
print(ans);
}
}K
对于4n就10011001...
4n+1就1001010011001...
4n+2就10010100101001...
4n+3就1001010010100101001...
小的情况特判即可
#include <bits/stdc++.h>
using namespace std;
int main(){
int n,i;
scanf("%d",&n);
if (n==2)printf("10\n");
else if (n==3)printf("Unlucky\n");
else if (n==6)printf("011001\n");
else if (n==7)printf("0110001\n");
else if (n==10)printf("1000000100\n");
else if (n==11)printf("00010000000\n");
else if (n==15)printf("010101001000000\n");
else{
if (n==5)printf("01000\n");
else{
if (n%4==0)
for (i=1;i<=n;i+=4)printf("1001");
else if (n%4==1){
printf("10010");
for (i=6;i<=n;i+=4)printf("1001");
}
else if (n%4==2){
printf("1001010010");
for (i=11;i<=n;i+=4)printf("1001");
}
else{
printf("100101001010010");
for (i=16;i<=n;i+=4)printf("1001");
}
printf("\n");
}
}
}
M
神仙构造。。。不是很懂。。。
#include <cstdio>
using namespace std;
int n;
int main(){
scanf("%d",&n);
printf("%.9lf\n",1.0/(n*((n+1)/2)*((n+2)/2)));
}
Comments | NOTHING