T1
考场用时：\(20\) min
期望得分：\(100\) pts
实际得分：\(100\) pts
求出所有上升子段，答案即为每个子段内第一个与最后一个深度差，注意第一个和最后一个要特殊处理。
#include<bits/stdc++.h>
#define ll long long
#define lc(k) k<<1
#define rc(k) k<<1|1
#define orz cout<<"I AK IOI\n"
//#define int long long
const int MAX=2e5+10;
const int MOD=998244353;
using namespace std;
inline char readchar() {
static char buf[100000], *p1 = buf, *p2 = buf;
return p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 100000, stdin), p1 == p2) ? EOF : *p1++;
}
inline int read() {
#define readchar getchar
int res = 0, f = 0;
char ch = readchar();
for(; !isdigit(ch); ch = readchar()) if(ch == '-') f = 1;
for(; isdigit(ch); ch = readchar()) res = (res << 1) + (res << 3) + (ch ^ '0');
return f ? -res : res;
}
inline void write(int x) {
if(x<0){putchar('-');x=-x;}
if(x>9) write(x/10);
putchar(x%10+'0');
}
int a[110],dp[25000+10];
signed main(){
int T=read();
while(T--){
int n=read(),mx=0;
memset(dp,-0x3f,sizeof dp);
for(int i=1;i<=n;i++){
a[i]=read();
mx=max(mx,a[i]);
}
// sort(a+1,a+1+n);
// n=unique(a+1,a+1+n)-a-1;
dp[0]=0;
for(int i=1;i<=n;i++)
for(int j=a[i];j<=mx;j++)
dp[j]=max(dp[j],dp[j-a[i]]+1);
int ans=0;
for(int i=1;i<=n;i++) ans+=(dp[a[i]]==1);
cout<<ans<<endl;
}
return 0;
}
T2
考场用时：\(40\) min
期望得分：\(100\) pts
实际得分：\(100\) pts
考虑 \(A\) 内某些面额是若是可以被其他的表示出来的，那它就是不必要的，直接背包求这个就行，复杂度 \(O(Tnv)\) 注意去重。
#include<bits/stdc++.h>
#define ll long long
#define lc(k) k<<1
#define rc(k) k<<1|1
#define orz cout<<"I AK IOI\n"
//#define int long long
const int MAX=2e5+10;
const int MOD=998244353;
using namespace std;
inline char readchar() {
static char buf[100000], *p1 = buf, *p2 = buf;
return p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 100000, stdin), p1 == p2) ? EOF : *p1++;
}
inline int read() {
#define readchar getchar
int res = 0, f = 0;
char ch = readchar();
for(; !isdigit(ch); ch = readchar()) if(ch == '-') f = 1;
for(; isdigit(ch); ch = readchar()) res = (res << 1) + (res << 3) + (ch ^ '0');
return f ? -res : res;
}
inline void write(int x) {
if(x<0){putchar('-');x=-x;}
if(x>9) write(x/10);
putchar(x%10+'0');
}
int a[110],dp[25000+10];
signed main(){
int T=read();
while(T--){
int n=read(),mx=0;
memset(dp,-0x3f,sizeof dp);
for(int i=1;i<=n;i++){
a[i]=read();
mx=max(mx,a[i]);
}
sort(a+1,a+1+n);
n=unique(a+1,a+1+n)-a-1;
dp[0]=0;
for(int i=1;i<=n;i++)
for(int j=a[i];j<=mx;j++)
dp[j]=max(dp[j],dp[j-a[i]]+1);
int ans=0;
for(int i=1;i<=n;i++) ans+=(dp[a[i]]==1);
cout<<ans<<endl;
}
return 0;
}
T3
考场用时：\(2\) h
期望得分：\(55\) pts
实际得分：\(55\) pts
写出 \(10\) 的暴力，然后菊花的部分直接 sort，链的部分二分，即可得到 \(55\) pts。
#include<bits/stdc++.h>
#define ll long long
#define lc(k) k<<1
#define rc(k) k<<1|1
#define orz cout<<"I AK IOI\n"
#define int long long
const int MAX=2e5+10;
const int MOD=998244353;
using namespace std;
inline char readchar() {
static char buf[100000], *p1 = buf, *p2 = buf;
return p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 100000, stdin), p1 == p2) ? EOF : *p1++;
}
inline int read() {
#define readchar getchar
int res = 0, f = 0;
char ch = readchar();
for(; !isdigit(ch); ch = readchar()) if(ch == '-') f = 1;
for(; isdigit(ch); ch = readchar()) res = (res << 1) + (res << 3) + (ch ^ '0');
return f ? -res : res;
}
inline void write(int x) {
if(x<0){putchar('-');x=-x;}
if(x>9) write(x/10);
putchar(x%10+'0');
}
int n,m,head[MAX],cnt;
struct node{int u,v,w,net;}e[MAX<<1];
void add(int u,int v,int w){
e[++cnt]=(node){u,v,w,head[u]};
head[u]=cnt;
return ;
}
queue<pair<int,int> > q;
#define mk make_pair
//namespace Sub1{
// int bl[110],sum[110];
// int ans=0,fa[110];
// int fid(int x){return fa[x]==x?x:fa[x]=fid(fa[x]);}
// void check(int fa,int k){
// for(int i=1;i<=n;i++) fa[i]=i;
// for(int i=1;i<=n;i++)
// if(fid(i)!=bl[i]) fa[fid(i)]=bl[i];
// for(int i=1;i<=n;i++)
// if(bl[i]&&fid(i)!=bl[i]) return 0;
// for(int i=1;i<=m;i++) sum[bl[i]]+=w[i];
// }
// void dfs(int stp){
// if(stp==n) return check(0,1),void();
// for(int i=1;i<=m;i++){
// bl[stp]=i;
// dfs(stp+1);
// bl[stp]=0;
// }
// return ;
// }
// void dfs1()
// void solve(){
// dfs(1);
// cout<<ans;
// return ;
// }
//}
namespace Sub2{
void solve(){
node e1[MAX];
int js=0;
for(int i=1;i<=cnt;i+=2) e1[++js]=e[i];
sort(e1+1,e1+1+js,[](node x,node y){
return x.w>y.w;
});
cout<<e[m].w;
return ;
}
}
namespace Sub3{
bool check(int lim){
int js=0;
for(int i=1,sum=0;i<=cnt;i+=2){
if(sum>=lim) js++,sum=0;
sum+=e[i].w;
}
return js>=m;
}
void solve(){
int l=1,r=10000,ans=0;
while(l<=r){
int mid=(l+r)>>1;
if(check(mid)) ans=mid,l=mid+1;
else r=mid-1;
}
cout<<ans;
return ;
}
}
signed main(){
int f1=1,f2=1;
n=read(),m=read();
for(int i=1;i<n;i++){
int u=read(),v=read(),w=read();
add(u,v,w);add(v,u,w);
f1&=(u==1);f2&=(v==u+1);
}
if(n<=10) Sub2::solve();
else if(f1) Sub2::solve();
else if(f2) Sub3::solve();
else Sub2::solve();
return 0;
}