Solution A(数据泄露):

因为数据范围只有500，且可能包含重边、自环和不连通，所以很容易想到flyod算法。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define imax 0x3f3f3f3f
#define lmax 0x3f3f3f3f3f3f3f3f

ll num[1005][1005];
int main(){

    ll n,m;
    cin>>n>>m;

    memset(num,0x3f,sizeof num);
    for(int i=1;i<=n;i++){
        num[i][i]=0;
    }
    for(int i=0;i<m;i++){
        ll a,b,s;
        cin>>a>>b>>s;
        num[a][b]=min(num[a][b],s);
        num[b][a]=min(num[b][a],s);
    }
    for(int k=1;k<=n;k++){
        for(int i=1;i<=n;i++){
            for(int j=1;j<=n;j++){
                if(num[i][k]<1e9&&num[k][j]<0x3f3f3f3f){
                    num[i][j]=min(num[i][j],num[i][k]+num[k][j]);
                }
            }
        }
    }
    int k;
    cin>>k;
    int start=1;
    ll re=0;
    for(int i=0;i<k;i++){
        int p;
        cin>>p;
        if(re==-1) continue;
        if(num[start][p]>1e9){
            re=-1;
            continue;
        }
        re+=num[start][p];
        start=p;
    }
    cout<<re<<endl;
    return 0;
}

Solution B(波格丹危机):

签到题，按照题意排序即可。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define imax 0x3f3f3f3f
#define lmax 0x3f3f3f3f3f3f3f3f
int main(){

    int n;
    cin>>n;
    vector<pair<int,string>> v;
    while(n--){
        string s;
        int a;
        cin>>s>>a;
        v.push_back({a,s});
    }
    sort(v.begin(),v.end());
    for(int i=0;i<v.size();i++){
        if(v[i].second=="."||v[i].second=="!") cout<<v[i].second<<endl;
        else cout<<v[i].second<<" ";
    }
    return 0;
}

Solution C(末日将至):

首先，如果发生全反射，说明一定能照射到全部数据包。

如果不能，当光照射在两个挡板交界处时，我们需要判断是否有数据包在光上面。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define imax 0x3f3f3f3f
#define lmax 0x3f3f3f3f3f3f3f3f
int main(){

    int T;
    cin>>T;
    while(T--){
        int a,b,n;
        double k;
        cin>>a>>b>>n>>k;
        pair<int,int> nums[n];
        for(int i=0;i<n;i++){
            cin>>nums[i].first>>nums[i].second;
        }
        double tana=(double)b/(double)a;
        double ana=atan(tana);
        double sina=sin(ana);
        double sinb=sina/k;
        bool c=0;
        if(fabs(sinb-1.0)>0.000001&&sinb>1.0){
            c=1;
        }
        if(c==1){
            cout<<"YES"<<endl;
            continue;
        }
        double k2=tan(asin(sinb));
        double b2=b-k2*a;
        bool f=1;
        for(int i=0;i<n;i++){
            double y1=k2*nums[i].first+b2;
            if(fabs(nums[i].second-y1)>0.000001&&nums[i].second>y1){
                f=0;
            }
        }
        if(f==1) cout<<"YES"<<endl;
        else cout<<"NO"<<endl;

    }
    return 0;
}

Solution D(Raksasa的摸der):

本题考虑对多种情况的判断。

例如：d ，de 会对后面的r的贡献产生影响。算区间的时候不能把前面的d，de考虑进去。

解题思路是按照多种情况考虑，算清楚所有情况即可。运用前缀和计数。

#include <bits/stdc++.h>
using namespace std;
#define inf 0x7ffffffffffffff
#define N 1005000
#define mod 1000000007
#define mod2 998244353
#define ll long long
char c[N];
ll der[N][3],er[N][2],r[N];
int main()
{
    ll n,x;
    scanf("%lld%lld",&n,&x);
    scanf("%s",c+1);
    ll ans=0;
    for(int i=1; i<=n; i++)
    {
        if(c[i]=='d')
        {
            der[i][0]=der[i-1][0]+1;
            der[i][1]=der[i-1][1];
            der[i][2]=der[i-1][2];
            er[i][0]=er[i-1][0];
            er[i][1]=er[i-1][1];
            r[i]=r[i-1];
        }
        else if(c[i]=='e')
        {
            der[i][0]=der[i-1][0];
            der[i][1]=der[i-1][1]+der[i-1][0];
            der[i][2]=der[i-1][2];
            er[i][0]=er[i-1][0]+1;
            er[i][1]=er[i-1][1];
            r[i]=r[i-1];
        }
        else if(c[i]=='r')
        {
            der[i][0]=der[i-1][0];
            der[i][1]=der[i-1][1];
            der[i][2]=der[i-1][2]+der[i-1][1];
            er[i][0]=er[i-1][0];
            er[i][1]=er[i-1][0]+er[i-1][1];
            r[i]=r[i-1]+1;
        }
        else
        {
            der[i][0]=der[i-1][0];
            der[i][1]=der[i-1][1];
            der[i][2]=der[i-1][2];
            er[i][0]=er[i-1][0];
            er[i][1]=er[i-1][1];
            r[i]=r[i-1];
        }
    }
    for(int i=x;i<=n;i++)
    {
        ans=max(ans,der[i][2]-der[i-x][2]-der[i-x][0]*(er[i][1]-er[i-x][1]-er[i-x][0]*(r[i]-r[i-x]))-der[i-x][1]*(r[i]-r[i-x]));
    }
    printf("%lld\n",ans);
    return 0;
}

也可以按区间一位一位算，这里给出验题人（Cantor.）的代码

#include<bits/stdc++.h>
#define oo 0x3f3f3f3f
#define OO 0x3f3f3f3f3f3f3f3f
#define LL long long
#define sz(x) int(x.size())
#define PII pair<int,int>
#define VI vector<int>
#define rep(i,l,r) for(int i=l;i<=r;++i)
#define STP system("pause")
using namespace std;
const int N=1e6;
void Solve(){
    int n,m;
    string s;
    cin>>n>>m>>s;
    vector<LL> f(6);
    //f0 = 'd' f1 = 'e' f2 = 'r' f3 = 'de' f4 = 'er' f5 = 'der'
    auto Add=[&](char x){
        if(x=='d')  f[0]+=1;
        if(x=='e')  f[1]+=1,f[3]+=f[0];
        if(x=='r')  f[2]+=1,f[4]+=f[1],f[5]+=f[3];
    };
    auto Delete=[&](char x){
        if(x=='d')  f[0]-=1,f[3]-=f[1],f[5]-=f[4];
        if(x=='e')  f[1]-=1,f[4]-=f[2];
        if(x=='r')  f[2]-=1;
    };
    auto Print=[&](){
        for(int i=0;i<6;++i)
            cout<<f[i]<<" \n"[i==5];
    };
    for(int i=0;i<m;++i){
        Add(s[i]);
    }
    LL ans=f[5];
    for(int i=m;i<n;++i){
        Delete(s[i-m]);
        Add(s[i]);
        ans=max(ans,f[5]);
    }
    cout<<ans<<'\n';
}
int main(){
    Solve();
}

Solution E(数圆圈):

对于任意1e18以内的数，我们迭代几十次以后都会变成0-1-0-1的循环。

所以我们迭代出0或1以后直接算就可以了。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define imax 0x3f3f3f3f
#define lmax 0x3f3f3f3f3f3f3f3f

ll f(ll num){
    string s=to_string(num);
    ll re=0;
    for(int i=0;i<s.size();i++){
        if(s[i]=='6'||s[i]=='9'||s[i]=='0')re++;
        if(s[i]=='8')re+=2;
    }
    return re;
}
int main() {
    int T;
    cin>>T;
    while(T--){
        ll n,k;
        cin>>n>>k;
        ll re=n;
        while(k){
            re=f(re);
            k--;
            if(re==0||re==1) break;
        }
        if(k%2==1){
            if(re==0) re=1;
            else re=0;
        }
        cout<<re<<endl;

    }
    return 0;
}

solution F(旅行):

考虑一个点在1-n某一条最短路径的条件，我们设dis(i,j)表示i到j的最短路径，如果点x在1-n的最短路径上，那么一定有dis(1,x)+dis(x,n)=dis(1,n)，考虑到数据只有只有10^3级别，所以我们可以从1-n每个点出发跑一遍堆优化dijkstra，对于输入的x直接判断,时间复杂度O((n+m)^2log(n+m)+m)。

​ 题解采用了另外一种做法。先正常建边以1号点为起点跑堆优化dijkstra，得到1到其他点的最短路径数组dis，然后建一张反图(如果存在边a->b，在反图中存在边b->a)，以n号点为起点跑堆优化dijkstra，得到n到其他点的最短路径数组dis1，则对于输入的x，我们直接判断dis(1,x)+dis1(n,x)是否等于dis(1,n)即可，时间复杂度O((n+m)log(n+m)+m)

#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
#define INF 2147483647
#define N 100005
#define M 200005
using namespace std ;
struct Edge { int nxt,to,dist ; } e[M],e1[M] ;
struct node {
    int id,d ;
    bool operator <(const node &a) const {
        return d>a.d ;
    }
};
int head[N],head1[N],tot1=0,tot=0 ;
int n,m,S ;
int dis[N],dis1[N] ;
bool vis[N] ;
priority_queue<node> q ;
inline void add(int from,int to,int dist) {
    e[++tot].to=to ; e[tot].dist=dist ;
    e[tot].nxt=head[from] ; head[from]=tot ;
}
inline void add1(int from,int to,int dist) {
    e1[++tot1].to=to ; e1[tot1].dist=dist ;
    e1[tot1].nxt=head1[from] ; head1[from]=tot1 ;
}
void dijkstra(int S) {
    fill(vis+1,vis+n+1,0) ;
    fill(dis+1,dis+n+1,INF) ;
    dis[S]=0 ; q.push((node){S,0}) ;
    while(!q.empty()) {
        node x=q.top() ; q.pop() ;
        if(vis[x.id]) continue ;
        vis[x.id]=1 ;
        for(int i=head[x.id];i;i=e[i].nxt) {
            int y=e[i].to ;
            if(dis[y]>dis[x.id]+e[i].dist) {
                dis[y]=dis[x.id]+e[i].dist ;
                if(!vis[y]) q.push((node){y,dis[y]}) ;
            }
        }
    }
}
void dijkstra1(int S) {
    fill(vis+1,vis+n+1,0) ;
    fill(dis1+1,dis1+n+1,INF) ;
    dis1[S]=0 ; q.push((node){S,0}) ;
    while(!q.empty()) {
        node x=q.top() ; q.pop() ;
        if(vis[x.id]) continue ;
        vis[x.id]=1 ;
        for(int i=head1[x.id];i;i=e1[i].nxt) {
            int y=e1[i].to ;
            if(dis1[y]>dis1[x.id]+e1[i].dist) {
                dis1[y]=dis1[x.id]+e1[i].dist ;
                if(!vis[y]) q.push((node){y,dis1[y]}) ;
            }
        }
    }
}
int main() {
    scanf("%d%d%d",&n,&m,&S) ;
    for(int i=1,u,v,w;i<=m;++i) {
        scanf("%d%d%d",&u,&v,&w) ;
        add(u,v,w) ; add1(v,u,w) ;
    }
    dijkstra(1) ;
    dijkstra1(n) ;
    while(S--)
    {
        int x ;
        scanf("%d",&x) ;
        if(1LL*dis[x]+dis1[x]==1LL*dis[n])
            printf("yes\n") ;
        else printf("no\n") ;
    }
    return 0 ;
}

Solution G(全体目光看向我，我宣布个事):

单纯的统计，实在不行也可以开26个变量来计数。

#include <bits/stdc++.h>
using namespace std;
#define inf 0x7ffffffffffffff
#define N 1005000
#define mod 1000000007
#define mod2 998244353
#define ll long long
ll buc[N];
int main()
{
    ll n;
    scanf("%lld",&n);
    for(int i=1;i<=n;i++)
    {
        char ch;
        scanf(" %c",&ch);
        buc[ch]++;
    }
    ll ans=0;
    char ch;
    for(int i='A';i<='Z';i++)
    {
        if(ans<buc[i])
        {
            ans=buc[i];
            ch=i;
        }
    }
    printf("%c",ch);
    return 0;
}

Solution H(寻找最大差值):

我们创建两个数组，第一个数组是从下标0到i的最小值，第二个数组是从最后面到i的最大值。

然后遍历这两个数组，使用最大值减去最小值即可。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define imax 0x3f3f3f3f
#define lmax 0x3f3f3f3f3f3f3f3f
int main(){

    int T;
    cin>>T;
    while(T--){
        int n;
        cin>>n;
        int num[n];
        for(int i=0;i<n;i++){
            cin>>num[i];
        }
        deque<int> mx;
        deque<int> mi;
        for(int i=0;i<n;i++){
            if(i==0) mi.push_back(num[0]);
            else{
                mi.push_back(min(mi.back(),num[i]));
            }
        }
        for(int i=n-1;i>=0;i--){
            if(i==n-1) mx.push_front(num[n-1]);
            else mx.push_front(max(num[i],mx.front()));
        }
        int re=-1;
        for(int i=0;i<n;i++){
            if(mx[i]>mi[i])re=max(re,mx[i]-mi[i]);
        }
        cout<<re<<endl;
    }
    return 0;
}

另一份代码：

#include <bits/stdc++.h>
using namespace std;
#define inf 0x7ffffffffffffff
#define N 1005000
#define mod 1000000007
#define mod2 998244353
#define ll long long
ll a[N];
int main()
{
    ll t;
    scanf("%lld",&t);
    while(t--)
    {
        ll n;
        scanf("%lld",&n);
        ll num=0;
        ll ans=-1;
        for(int i=0;i<n;i++) scanf("%lld",&a[i]);
        for(int i=n-1; i>=0; i--)
        {
            num=max(a[i],num);
            if(num-a[i]>0) ans=max(num-a[i],ans);
        }
        printf("%lld\n",ans);
    }

    return 0;
}

solution I(彩虹) :

7种颜色染格子，要求相邻格子颜色不相同，求染色的方案数。

​ 经典状压dp。

​ 我们令dp(i,j)表示第i行状态为j的染色方案数，其中状态j模拟一个n位7进制数，第k位为0-6分别代表格子(i,k)上的颜色为第1-7种颜色，则有dp转移方程
$$
​ 但是本题要注意处理一下一行的合法颜色，不然会TLE

#include<bits/stdc++.h>
#define N 65536
#define mod 1000000007
#define LL long long
using namespace std ;
int q[N],n,m,num=0 ;
LL f[15][N] ;
bool check(int len,int x,int y)
{
    int s,t ;
    while(len--)
    {
        s=x%7,t=y%7 ;
        if(s==t) return false ;
        x/=7 ; y/=7 ;
    }
    return true ;
}
int main()
{
    cin>>n>>m ;
    int res=1 ;
    for(int i=1;i<=n;++i) res*=7 ;
    for(int i=0;i<res;++i)
    {
        int len=n,s=i/7,lst=i%7 ;
        bool flag=1 ;
        while(--len)
        {
            if(s%7==lst) 
            {
                flag=0 ;
                break ;
            }
            lst=s%7 ; s/=7 ;
        }
        if(flag) q[++num]=i ;
    }
    memset(f,0,sizeof(f)) ;
    for(int i=1;i<=num;++i) f[1][i]=1 ;
    for(int i=2;i<=m;++i)
    {
        for(int j=1;j<=num;j++)
            for(int k=1;k<=num;++k)
                if(check(n,q[j],q[k]))
                    f[i][j]=(f[i][j]+f[i-1][k])%mod ;
    }
    LL ans=0 ;
    for(int i=1;i<=num;++i)
        ans=(ans+f[m][i])%mod ;
    cout<<ans<<endl ;
    return 0 ;
} 

Solution J(突然的自我):

签到题，根据题意，很容易推出f(i)=f(i-1)+f(i-2)+1。

Solution K(Raksasa的轻功):

因为跳法的原因，可以判断出具有传递性。

提供两种思路：

一种是判断高低，记录每一座山峰往左和往右能跳到的最低山峰位置

#include <bits/stdc++.h>
using namespace std;
#define inf 0x7ffffffffffffff
#define N 1005000
#define mod 1000000007
#define mod2 998244353
#define ll long long
ll a[N];
ll pre[N],suf[N];
int main()
{
    ll n;
    scanf("%lld",&n);
    for(int i=1;i<=n;i++) scanf("%lld",&a[i]);
    ll mark=1;
    for(int i=1;i<=n;i++)
    {
        if(a[i]>a[i-1]) pre[i]=mark;
        else pre[i]=mark=i;
    }
    mark=n;
    for(int i=n;i>=1;i--)
    {
        if(a[i]>a[i+1]) suf[i]=mark;
        else suf[i]=mark=i;
    }
    ll ans=0;
    for(int i=1;i<=n;i++) ans=max({ans,i-pre[i],suf[i]-i});
    printf("%lld\n",ans);
    return 0;
}

另一种是直接从左跑到右，从右跑到左，各跑一遍。

#include <bits/stdc++.h>
using namespace std;
#define inf 0x7ffffffffffffff
#define N 1005000
#define mod 1000000007
#define mod2 998244353
#define ll long long
ll a[N];
int main()
{
    ll n;
    scanf("%lld",&n);
    for(int i=1;i<=n;i++) scanf("%lld",&a[i]);
    ll up=0,down=0;
    ll ans=0;
    for(int i=1;i<n;i++)
    {
        if(a[i]<a[i+1])
        {
            up++;
            down=0;
        }
        else if(a[i]>a[i+1])
        {
            down++;
            up=0;
        }
        else
        {
            up=0;
            down=0;
        }
        ans=max({ans,up,down});
    }
    printf("%lld\n",ans);
    return 0;
}

solution L(函数求和):

一句话题意:
$$
​ 所以

​
$$
​ 直接求和取模即可，时间复杂度O(m)

#include<bits/stdc++.h>
#define N 10000005
#define mod 1000000007
#define LL long long
using namespace std ;
int a[N],c[N],n,m ;
inline void read(int &num)
{
   int s = 0 ; char ch = getchar();
   while(ch < '0' || ch > '9') ch = getchar(); 
   while(ch >= '0' && ch <= '9') s = (s<<3) + (s<<1) + ch - '0', ch = getchar();
   num = s;
}//快读，可以用scanf代替
int main() {
    int n,m ;
    read(n),read(m) ;
    for(int i=1;i<=n;++i) read(a[i]) ;
    LL ans=0 ; int x ;
    while(m--)
    {
        read(x) ; LL res ;
        if(x==a[x]) res=x ;
        else res=1 ;
        ans=(ans+res)%mod ;
    }
    printf("%lld\n",ans) ;
    return 0 ;
}

Solution M(Raksasa的棋局):

本题可以预处理出馬踩的所有的位置最快需要多少步（bfs），将其存储在数组中，O(1)查询即可

#include <bits/stdc++.h>
using namespace std;
#define inf 0x7ffffffffffffff
#define N 1010
#define mod 1000000007
#define mod2 998244353
#define ll long long
ll dp[N][N];
ll dx[8]={1,2,2,1,-1,-2,-2,-1};
ll dy[8]={-2,-1,1,2,-2,-1,1,2};//馬的8个走向
int main()
{
    ll n,m,q;
    scanf("%lld%lld%lld",&n,&m,&q);
    ll x1,y1;
    scanf("%lld%lld",&x1,&y1);
    queue<pair<ll,ll>> qu;
    qu.push({x1,y1});
    while(!qu.empty())
    {
        pair<ll,ll> pa=qu.front();
        qu.pop();
        for(int i=0;i<8;i++)
        {
            ll x=pa.first+dx[i];
            ll y=pa.second+dy[i];
            if(x==x1&&y==y1) continue;
            if(x<1||x>n||y<1||y>m) continue;
            if(!dp[x][y])
            {
                dp[x][y]=dp[pa.first][pa.second]+1;
                qu.push({x,y});
            }
        }
    }
    while(q--)
    {
        ll x,y;
        scanf("%lld%lld",&x,&y);
        if(dp[x][y]) printf("%lld\n",dp[x][y]);
        else printf("-1\n");
    }
    return 0;
}

Solution N(Raksasa的数字):

把数组中每一个数字都转换成二进制，异或1会把数字“翻转”

例如： 1 异或 1为0，0异或 1 为 1。

统计每一位（转换成二进制）上有多少个1和0，因为异或1会把所有的1变成0,0变成1。所有就等同于1和0的数目交换。所有就算一下性价比，尽量往小的换即可。

#include <bits/stdc++.h>
using namespace std;
#define inf 0x7ffffffffffffff
#define N 1005000
#define mod 1000000007
#define mod2 998244353
#define ll long long
vector<bitset<32>> ve;
ll cnt[32];
int main()
{
    ll t;
    scanf("%lld",&t);
    while(t--)
    {
        ll n;
        ve.clear();
        scanf("%lld",&n);
        for(int i=0;i<n;i++)
        {
            ll x;
            scanf("%lld",&x);
            bitset<32> bi(x);
            ve.push_back(bi);
        }
        memset(cnt,0,sizeof(cnt));
        for(int i=0;i<n;i++)
        {
            for(int j=0;j<32;j++)
            {
                if(ve[i][j]) cnt[j]++;
            }
        }
        ll ans=0;
        for(int i=0;i<32;i++)
        {
            if(cnt[i]>n/2)
            {
                ans+=(1ll<<i);
            }
        }
        printf("%lld\n",ans);
    }
    return 0;
}