ABC - 162 - F - Select Half (DP&奇偶性） 题目传送门 思路：  #include<bits/stdc++.h> using namespace std; typedef long long ll; const int N=2e5+5; ll a[N],dp[N],sum[N]; int main(){ int n; scanf("%d",&n); for(int i=1,x;i<=n;i++){ scanf("%lld",&a[i]); sum[i]=(i>2?sum[i-2...

ABC - 162 - E - Sum of gcd of Tuples (Hard) （DP&数论) 思路：  AC代码： #include<bits/stdc++.h> using namespace std; typedef long long ll; const int N=1e5+5,mod=1e9+7; ll ksm(ll a,ll b){//快速幂  ll ans=1; while(b){ if(b&1) ans=ans*a%mod; a=a*a%mod; b>>=1; } return ans; } ll f[N],ans=0; int ...

E1. Three Blocks Palindrome (easy version) （暴力&前缀和） 题意传送门 思路：  AC代码： #include<bits/stdc++.h> using namespace std; int a[27][3000]; int main(){ int t,n,ans; scanf("%d",&t); while(t--){ ans=0; scanf("%d",&n); for(int i=1,x;i<=n;i++) { scanf("%d",&...

E2. Three Blocks Palindrome (hard version) (贪心&暴力) 题目传送门 思路：  AC代码： #include<bits/stdc++.h> using namespace std; int main(){ int t,n; scanf("%d",&t); while(t--){ scanf("%d",&n); vector<vector<int> >a(201,vector<int>(n+1)); vector<vector<i...

交互题 : 1. Guess the Number(二分） 题目传送门 题意：给定1------1e6的范围的一个数,要你在规定次数内猜出该数。 思路：  AC代码： #include<bits/stdc++.h> using namespace std; int main(){ int l=1,r=1e6; while(l!=r){ int mid=(l+r+1)>>1;//这里要用(l+r+1) 因为是跟"<"和">="比较,如果l=mid ans=r=l+1 则会一直循环.  printf("%d\n&...

交互题 B. Lost Numbers(暴力） 题目传送门 思路：  AC代码： #include<bits/stdc++.h> using namespace std; int q[5]; int a[7]={0,4,8,15,16,23,42}; int main(){ for(int i=1;i<=4;i++) { printf("? %d %d\n",i,i+1); fflush(stdout); int x; scanf("%d",&x); q[i]=x; } do{ if(a[1]*a[2]==q[1]&&a...

交互题 : A. Bear and Prime 100 （数论） 题目传送门 思路：  AC代码： #include<bits/stdc++.h> using namespace std; int p[20]={2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,4,9,25,49};//一个大于1的数的最小因子是素数。  int main(){//一个合数能分解至少两个质因数(可以相同)相乘 (4,9,25,49)的情况考虑.  int cnt=0; for(int i=0;i<19;i++){ printf("%d\n",...

C. Linova and Kingdom (DFS&贪心） 题目传送门 思路：  AC代码： #include<bits/stdc++.h> using namespace std; typedef long long ll; const int N=2e5+5; #define mst(a) memset(a,0,sizeof a) vector<int>ans; vector<int>e[N]; int dfs(int u,int fa,int d){ int sz=1; for(auto v:e[u]){ if(v==fa) continue...

D. Xenia and Colorful Gems （排序&贪心) 题目传送门 思路：  #include<bits/stdc++.h> using namespace std; typedef long long ll; const int N=1e5+5; #define mst(a) memset(a,0,sizeof a) int a[3][N]; ll cal(int i,int j,int k){ return (ll)(a[0][i]-a[1][j])*(a[0][i]-a[1][j])+(ll)(a[1][j]-a[2][k])*(a[1][j]-a[2]...

P2858 [USACO06FEB]Treats for the Cows G/S （区间DP) 题目传送门 思路：  AC代码： #include<bits/stdc++.h> using namespace std; typedef long long ll; const int N=2e3+5; int v[N],dp[N][N]; int main(){ int n; scanf("%d",&n); for(int i=1;i<=n;i++) scanf("%d",&v[i]); for(int i=1,len=...

P3146 [USACO16OPEN]248 G （区间DP） 题目传送门 思路：  AC代码： #include<bits/stdc++.h> using namespace std; typedef long long ll; const int N=300; int a[N],dp[N][N]; int main(){ int n; scanf("%d",&n); for(int i=1;i<=n;i++) scanf("%d",&a[i]),dp[i][i]=a[i]; int ans=0; for(int le...

P1091 合唱队形 (DP&LIS) 题目传送门 思路：显然正反跑两边LIS，遍历一遍取最值即可。时间复杂度：O（n^2) 不过可以用upper_bound()压到O(nlogn)这里就不写这种做法了。。。。 AC代码： #include<bits/stdc++.h> using namespace std; const int N=105; int a[N],dp[2][N];//保存[1,n]和[n,1]的LIS  int main(){ int n; scanf("%d",&n); for(int i=1;i<=n;i++) sca...

P1198 [JSOI2008]最大数 （逆ST） 题目传送门 思路：建立一个逆ST表,从右到左的区间查询, 每次插入一个数就更新一次区间最值,然后区间查询用RMQ实现就行. AC代码： #include<bits/stdc++.h> using namespace std; const int N=2e5+5; int t,id; typedef long long ll; ll mod,a[N],pre,f[N][20]; ll que(int len){ //ST区间查询.(query) int k=0,l=id-len+1; while((1<<k)*2<...

由日期推星期（基姆拉尔森计算公式） 题意：给定年月日，问该天是星期几。 思路：运用基姆拉尔森计算公式立即得。 代码： #include<cstdio> #include<cstring>  using namespace std; int week(int y,int m,int d){ if(m<3) y--,m+=12; return (d+2*m+3*(m+1)/5+y+y/4-y/100+y/400+1)%7;//注意0代表星期天 } char s[10][10]={"天","一","二",&qu...