感觉还要多练，有的题思路不难，但是赛时就没思路。
A
const int N=110,M=1e4+10;
int dp[N][M];
void solve(){int n,m;cin>>n>>m;vector<int>a(n+1);forr(i,1,n){cin>>a[i];}dp[0][0]=1;//没钱 没菜 就是一种情况forr(i,1,n){reforr(j,0,m){dp[i][j]=dp[i-1][j];//没买if(j>=a[i])dp[i][j]+=dp[i-1][j-a[i]];//买了}}// forr(i,1,n){// forr(j,1,m)cout<<dp[i][j]<<' ';// cout<<endl;// }cout<<dp[n][m];
}
E
- 注意 x , y x,y x,y是两个非负整数
- 让 ∣ x 2 + y 2 − D ∣ \lvert x^2+y^2-D\rvert ∣x2+y2−D∣最小，就是找 x 2 + y 2 x^2+y^2 x2+y2最接近 D D D
- 若 x 2 + y 2 = D x^2+y^2=D x2+y2=D，用一个数表示另一个数 x = D − y 2 x=\sqrt{D-y^2} x=D−y2
- 如果 x 2 + y 2 ≤ D x^2+y^2\leq D x2+y2≤D， x = ⌊ D − y 2 ⌋ x=\lfloor\sqrt{D-y^2}\rfloor x=⌊D−y2⌋
- 要么 x 2 + y 2 ≥ D x^2+y^2\geq D x2+y2≥D， x = ⌈ D − y 2 ⌉ x=\lceil\sqrt{D-y^2}\rceil x=⌈D−y2⌉
- 这是最接近 D D D时 x x x的取值 看这两种那个离 D D D最近
- 并且这也限制了 0 < y < D 0<y<\sqrt{D} 0<y<D
两个正整数这类的题，这两变量一定会相互牵制，缩小范围
const int N=2e12;
void solve(){int d;cin>>d;int ans=N;for(int y=1;y*y<=d;y++){int xc=ceil(sqrt(d-y*y));int xf=floor(sqrt(d-y*y));ans=min(min(abs(xc*xc+y*y-d),abs(xf*xf+y*y-d)),ans);}cout<<ans<<endl;
}
G
打赛的时候没读明白题
题意
找一条路径走四个点 中间跳两次 中间两个点不能被跳过
思路
- 确定 一个路径及其两头的点 为中间经过的点
- 这两头的点度数都应该 ≥ 2 \geq 2 ≥2
- 再从两头的点确定起点和终点
const int N=1e4+10,M=1e5+10;
int n,m;
int u[M],v[M];
map<int,int>deg;
void solve(){cin>>n>>m;forr(i,1,m){cin>>u[i]>>v[i];deg[v[i]]++,deg[u[i]]++;}// for(auto i:deg)cout<<i.first<<' '<<i.second<<endl;int ans=0;forr(i,1,m){ans+=((deg[u[i]]-1)*(deg[v[i]]-1));}cout<<ans*2<<endl;//逆转也可以是一种解 别急 有反转
}
J
一开始的模拟做法tle了
所以需要一步给出应该达到的数字
set做法
set方法lower_bound(int a) 返回第一个大于等于a的数的迭代器位置
set<int>s;
void solve(){//set存没出现过的数字forr(i,1,1e5+1e6)s.insert(i);//极限情况 1e5个数都是1e6int n;cin>>n;forr(i,1,n){// cin>>a[i];int a;cin>>a;set<int>::iterator it=s.lower_bound(a);s.erase(*it);//去除出现过的数字cout<<*it<<' ';}cout<<endl;
}
并查集做法
- 初始化 每个数 a i a_i ai的根就是自身
- 每次出现过某数 a i a_i ai 就让fa[ a i a_i ai]= a i a_i ai现在的根+1
- 此时fa[ a i a_i ai]的数可能也会和前面的重复 但是还会再find()一次 找到的根一定是不会重复的
更详细的过程
const int N=1e5+1e6;
int fa[N];
int find(int x){if(x==fa[x])return x;return fa[x]=find(fa[x]);
}
void solve(){forr(i,1,1e5+1e6)fa[i]=i;int n;cin>>n;forr(i,1,n){int a;cin>>a;int f=find(a);fa[f]=find(f)+1;cout<<f<<' ';}
}
