T1
用时:\(20\) min
要求统计数组 \(a\) 中有序三元组 \((x,y,z)\) 的个数,满足 \(\gcd(a_x,a_y)=a_z\),直接枚举 \(x\),\(y\),将 \(x\) 后面的加入一个 map 中,统计答案即可。
#include<bits/stdc++.h>
#define ll long long
//#define int long long
//#define ull unsigned long long
#define lc(k) k<<1
#define rc(k) k<<1|1
#define lb lower_bound
#define orz cout<<"gzn ak ioi\n"
const int MAX=1e6+10;
const int MOD=1e9+7;
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');
}
map<int,int> mp;
int a[3010];
signed main(){
// freopen("1.in","r",stdin);
// freopen("mobius.in","r",stdin);
// freopen("mobius.out","w",stdout);
int n=read();
for(register int i=1;i<=n;i++) a[i]=read();
ll sum=0;
for(register int i=1;i<=n;i++){
mp.clear();
for(register int j=i+1;j<=n;j++) mp[a[j]]++;
for(register int j=i+1;j<=n;j++){
mp[a[j]]--;
sum+=(mp[__gcd(a[i],a[j])]);
}
}
cout<<sum;
return 0;
}
/*
5
6 4 9 2 3
*/
T2
用时:\(20\) min
一个比较板的二分套 dp,当 \(k\) 能够满足时,\(k+1\) 一定也能够满足,所以具有单调性,考虑二分,check时一个dp统计最长合法子序列长度是否 \(\ge m\) 即可。
#include<bits/stdc++.h>
#define ll long long
//#define int long long
//#define ull unsigned long long
#define lc(k) k<<1
#define rc(k) k<<1|1
#define lb lower_bound
#define orz cout<<"gzn ak ioi\n"
const int MAX=1e6+10;
const int MOD=1e9+7;
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');
}
/*
显然若k满足,k+1一定满足,考虑二分这个k
dp[i]表示以i结尾,符合条件的最长长度
dp[i]=max(dp[j])+1 1<=j<i |a[j]-a[i]|<=k
期望100pts
*/
int n,m,a[1010],dp[1010];
bool check(int k){
int ret=1;
for(int i=1;i<=n;i++){
dp[i]=1;
for(int j=1;j<i;j++)
if(abs(a[j]-a[i])<=k)
dp[i]=max(dp[i],dp[j]+1);
ret=max(ret,dp[i]);
}
return ret>=m;
}
signed main(){
// freopen("cauchy.in","r",stdin);
// freopen("cauchy.out","w",stdout);
int l=1,r=2e9,ans=0;
n=read(),m=read();
for(int i=1;i<=n;i++) a[i]=read();
while(l<=r){
int mid=(l+r)>>1;
if(check(mid)){
ans=mid;
r=mid-1;
}
else l=mid+1;
}
cout<<ans;
return 0;
}
T3
用时:\(1.5\) h
发现由于题目的限制,必须要在一棵子树全部处理完成之后再去处理别的子树,所以这可以 dp。
这题用的时间比较久,在考场上想到一点思路,当时也考虑到了应该贪心的按 dp 值或者是剩余石子数来排序,但是没想打其实是按照 \(dp-w\) 来排序,然后 dp,由于细节太多,打了一个暴力就跑路了。
但实际上真正理解之后写起来并不难写。
标签:10,10.23,报告,int,long,解题,freopen,dp,define From: https://www.cnblogs.com/wapmhac/p/16823401.html