我以为我做的最后一套是15，没想到还有机会做一套

第一题填空
只要知道arctan和弧长公式就能做
弧长公式 $l = α * r$

c++中求α要用反三角函数，其中arcsin=asin，arccos=acos，arctan=atan

注意在使用时默认是弧度制，如果是角度制要先转化为弧度制以下是公式

ps：或者直接用电脑自带的计算器，也能嗯出来，个人感觉比程序好使

第二题填空
不是很会，还没看，回头看了补上

第一题
找规律的题，只要给的数大于1，最终结果就加1

#include <bits/stdc++.h>
using namespace std;
int main(){
    int n ;
    int res = 0;
    cin >> n;
    for(int i = 0;i < n;i++){
        long long a;
        cin >> a;
        if(a != 1){
            res ++;
        }
    }
    cout << res << endl; 
    return 0;
}

第二题
感觉还是得看一下规律，在不断计算的过程中肯定会相等的，相等时，就停止计算直接输出

#include <bits/stdc++.h>
using namespace std;

void solve(){
    long long a,b,c;
    int k;
    cin >> a >> b >> c >> k;
    for(int i = 0;i < k;i++){
        long long tempa = (b+c) / 2;
        long long tempb = (a+c) / 2;
        long long tempc = (a+b) / 2;
        a = tempa;
        b = tempb;
        c = tempc;
        if(tempa == tempb && tempb == tempc) break;
    }
    cout << a << " " << b << " " << c << '\n';
}

int main(){
    int T;
    cin >> T;
    while(T--){
        solve();
    } 
    return 0;
}

第三题 画展布置
这道题给了一个累加平方差，很明显可以削，最终只剩一头一尾，可惜当时没仔细看，直接暴力写的，拿了一半

正解是滑动窗口，直接算端口值，并记录最小的L（记得排序）

//正解：化简公式，滑动窗口
#include <bits/stdc++.h>
const int N = 1e5+10;
long long a[N];
using namespace std;
int main(){
    int n,m;
    cin >> n >> m;
    for(int i = 0;i < n;i++){
        cin >> a[i];
    }
    sort(a,a+n);
    long long ans = LLONG_MAX;//要开LLONG_MAX或者1e10以上否则报错 
    for(int i = m - 1;i < n;i++){
        ans = min(ans,a[i]*a[i]-a[i-m+1]*a[i-m+1]);
    }
    cout << ans << endl;
}



//错解：遍历写，只能拿55分 (开longlong能拿80)
//#include <bits/stdc++.h>
//using namespace std;
//const int N = 1e5+10;
//long long a[N];
//int n,m;
//long long ans = LLONG_MAX;
//
//long long compe(int u){
//  long long res = 0;
//  for(int i = u;i < u + m - 1;i++){
//      long long x = a[i+1] * a[i+1] * 1ll;
//      long long y = a[i] * a[i] * 1ll;
//      res += x - y;
//  }
//  return res;
//}
//
//int main(){
//  cin >> n >> m;
//  for(int i = 0;i < n;i++){
//      cin >> a[i];
//  }
//  
//  sort(a,a+n);
//  
//  for(int i = 0;i < n - m + 1;i++){
//      long long res = compe(i);
//      ans = min(ans,res);
//  }
//  cout << ans << endl;
//} 

第四题 水质检测
这道题一开始往dfs想了，怎么都想不出来，后来联想到dp，最后还是找规律。

找出第一个出现#的下标，和最后一个出现的#的下标，并计算a、b在这个下标之间哪个.的数量较少，作为答案输出。这样写能拿45分，如果加一个bfs初始化时判断是否连通，可以多拿10分。

正解是模拟或者dp，这里因为我dp不好，只看了模拟

以上规律是洛谷题解给的， 传送门

#include <bits/stdc++.h>
using namespace std;

int main(){
    string a,b;
    cin >> a >> b;
    int len = a.size();
    int l = len,r = 0;
    int ans = 0;

    for(int i = 0;i < a.size();i++){
        if(a[i] == '#' || b[i] == '#'){
            l = min(l,i);
            r = max(r,i);
        }
    }

    for(int i = l;i < r;i++){
        if(a[i] == '#' && a[i + 1] == '.' && b[i] == '.'){
            a[i+1] = '#';
            ans++;
        }
        if(a[i] == '.' && b[i] == '#' && b[i+1] == '.'){
            b[i+1] = '#';
            ans++;
        }
        if(a[i] == '#' && b[i] == '#' && a[i + 1] == '.' && b[i+1] == '.'){
            int t = i + 1;
            while(a[t] != '#' && b[t] != '#'){
                t++;
            }
            if(a[t] == '#'){
                a[i+1] = '#';
                ans++;
            }else{
                b[i+1] = '#';
                ans++;
            }
        }
    }
    cout << ans << endl;
} 

//找到一个普遍规律可以拿50分 ,如果开局bfs判断是否一开始就连通，那么可以多拿10分 
//#include <bits/stdc++.h>
//using namespace std;
//const int N = 1e6+10;
//int da[N],db[N];
//int n;
//bool st[N];
//int fst,ed;
//int res;
//int ans;
//int main(){
//  string a,b;
//  cin >> a;
//  cin >> b;
//  a = "%" + a;
//  b = "%" + b;
//  
//  for(int i = 1; i <= a.size();i++){
//      if(a[i] == '#' || b[i] == '#'){
//          fst = i;
//          break;
//      }
//  }
//  for(int i = a.size();i >= 1;i--){
//      if(a[i] == '#' || b[i] == '#'){
//          ed = i;
//          break;
//      }
//  }
//  
//  for(int i = 1;i <= a.size();i++){
//      if(a[i] == '.') da[i] = da[i - 1] + 1;
//      else da[i] = da[i - 1];
//  }
//  
//  for(int i = 1;i <= b.size();i++){
//      if(b[i] == '.') db[i] = db[i - 1] + 1;
//      else db[i] = db[i - 1];
//  }
//  
//  res = min((db[ed] - db[fst]),(da[ed]-da[fst]));
//  cout << res << endl;
//}

第五题
树状dp+背包问题
暂时没写....

第六题
暴力dfs没写出来，因为那个优先级不是很会考虑

正解是找规律，发现有+-两种算法，最终都会被削去，只有连续异或的数组成的异或块会存在，并且最终相加的时候每一个异或块会算2*3^(n-i-1)次。

用pre数组快速求得异或块，p数组储存3的幂次，最后再累加

这里有一个特例就是当全部数都被异或相连的时候，只算了一次，所以将ans初始化为pre[n]正合适

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e5+10;
//pre是前i个元素组成的异或块..p是3的i次方 
ll pre[N],p[N],a[N],ans,mod = 1e9+7;
int main(){
    int n;
    cin >> n;
    for(int i = 1;i <= n;i++) cin >> a[i];
    p[0] = 1;
    for(int i = 1;i <= n;i++) pre[i] = pre[i-1]^a[i],p[i]=p[i-1]%mod*3;
    ans = pre[n];
    for(int i = 1;i <= n;i++) ans = ans%mod + (2 * p[n - i - 1] %mod)*pre[i]%mod;
    cout << (ans%mod+mod)%mod;
}