比赛链接：https://codeforc.es/contest/1703
这次比赛做了ABCE四个题，其中D和F题疯狂TLE，我很无语。比赛的难度并不大，最后一题没有看应该是个dp问题，f题是个dp的前置题，有dp的思想在里面。
A题：if else 水题
code:
#include<bits/stdc++.h>
using namespace std;
int main()
{
int t;
cin>>t;
while(t--)
{
string a;
cin>>a;
if((a[0]=='y'||a[0]=='Y')&&(a[1]=='e'||a[1]=='E')&&(a[2]=='s'||a[2]=='S'))
printf("YES\n");
else
printf("NO\n");
}
}
B题：大意就是给一个字符串找出出现不同类别的数量然后加上总数就OK了
code:
#include<bits/stdc++.h>
using namespace std;
int sign[26];
int main()
{
int t;
cin>>t;
while(t--)
{
memset(sign,0,sizeof sign);
int n;
scanf("%d",&n);
string a;
cin>>a;
for(int i=0;i<a.size();i++)
{
sign[a[i]-65]=1;
}
int sum = 0;
for(int i=0;i<26;i++)
if(sign[i]) sum++;
printf("%d\n",sum+a.size());
}
}
C题：给出几个数，每个数给出一些操作，然后反向一下。U将数字-1，D+1，这里需要理解题意。然后输出就OK了
code:
#include<bits/stdc++.h>
using namespace std;
int a[110];
int main()
{
int t;
cin>>t;
while(t--)
{
int n;
scanf("%d",&n);
for(int i=1;i<=n;i++)
scanf("%d",&a[i]);
int x;
string b;
for(int i=1;i<=n;i++)
{
scanf("%d",&x);
cin>>b;
// cout<<"!"<<b.size()<<"!";
for(int j=0;j<b.size();j++)
{
if(b[j]=='D')
{
a[i]++;
if(a[i]==10) a[i]=0;
if(a[i]==-1) a[i]=9;
}
if(b[j]=='U')
{
a[i]--;
if(a[i]==10) a[i]=0;
if(a[i]==-1) a[i]=9;
}
}
}
for(int i=1;i<=n;i++)
printf("%d ",a[i]);
printf("\n");
}
}
D题：这道题就是我TLE的题，比赛的时候钻牛角尖了，这个题就是给出很多字符串，求每个字符串是否能被其他两个字符串相加所得到。字符串长度“不超过8”。
解决方法：这个题需要注意的点就是长度不超过8。这个数据量很小，所以应该从这里开始分割，这么一看，最多也就只有7种可能。我们可以把每个字符串都放到set里面，这个操作是nlogn，然后我们分割每一个字符去寻找，这里最多也是7*nlogn。正解就是nlogn了。我自己想到n^2logn的那种算法。其实完全可以将其中n用长度来入手。
code:
#include<bits/stdc++.h>
using namespace std;
const int nn = 1e5+10;
string a[nn];
int num[nn];
set<string> se;
int main()
{
int t;
cin>>t;
while(t--)
{
memset(num,0,sizeof num);
se.clear();
for(int i=0;i<nn;i++)
a[i].clear();
int n;
scanf("%d",&n);
for(int i=1;i<=n;i++)
{
cin>>a[i];
se.insert(a[i]);
}
for(int i=1;i<=n;i++)
{
for(int j=1;j<a[i].size();j++)
{
if(se.find(a[i].substr(0,j))!=se.end()&&se.find(a[i].substr(j,a[i].size()-j))!=se.end())
{
num[i] = 1;
break;
}
}
}
for(int i=1;i<=n;i++)
printf("%d",num[i]);
printf("\n");
}
}
E题：推导题，有点类似之前做过的黑白块题。大意就是给出一个n*n的矩阵，元素都是0 或 1 ，求我们最少改变多少块元素，可以使得这个矩阵0 90 180 270 360旋转和它本身一致。
解决方法：这个题就是可以从一个元素入手，然后推导出其他三个旋转后的替代点，然后暴力一下这个矩阵，需要改变的元素是4个点中出现次数最少的0或1，可以令4个点相加，这样就是1个数量，那么4-这个数，就是0的数量，然后对比。最后答案除以4。
code:
#include<bits/stdc++.h>
using namespace std;
string a[110];
int main()
{
int t;
cin>>t;
while(t--)
{
for(int i=0;i<110;i++)
a[i].clear();
int n,sum=0;
scanf("%d",&n);
for(int i=0;i<n;i++)
cin>>a[i];
n--;
for(int i=0;i<=n;i++)
for(int j=0;j<=n;j++)// 0,0 2,0 2,2 0,2
{
if(a[i][j]!=a[n-j][i]||a[i][j]!=a[n-i][n-j]||a[i][j]!=a[n-(n-j)][n-i])
{
int possum = (a[i][j]+a[n-j][i]+a[n-i][n-j]+a[n-(n-j)][n-i])-48*4;
sum+=min(possum,4-possum);
}
}
printf("%d\n",sum/4);
}
}
F题：这个题是个前缀后缀和二分的题。大意是，给出一组数据，对于一个i<j来说，a[i]<i<a[j]<j，让我们找有多少对这样的数据。
解决方法：另开一个数组，记录这个位置之前有多少已经满足a[i]<i，因为当a[j]>i时，那么i之前所有满足a[i]<i的元素都可以满足。所以可以用前缀和思想解题。
另外一种方法就是二分解决。用一个数组存储满足a[i]<i的数，然后每次遇到一个a[i]<i，我们去对比之前已经存在的满足数据，然后通过a[j]的大小和之前存在的[i]进行一个对比，找到地址后一相减就可以知道之前有多少个数了然后再存储j下标，由于存储的都是下标，所以是有序的可以二分。
前缀code:
#include<bits/stdc++.h>
using namespace std;
const int nn = 2*1e5 +10;
#define ll long long
ll v[nn];
int main()
{
int t;
cin>>t;
while(t--)
{
memset(v,0,sizeof v);
ll n,k,sum=0;
cin>>n;
for(ll i=1;i<=n;i++)
{
cin>>k;
v[i] = v[i-1];
if(k<i)
v[i]++,sum+=v[k-1];
}
cout<<sum<<endl;
}
}
二分code:
#include <bits/stdc++.h>
using namespace std;
const int MAX = 200007;
const int MOD = 1000000007;
void solve() {
int n;
cin >> n;
int a[n + 1];
for (int i = 1; i <= n; i++) {
cin >> a[i];
}
long long res = 0;
vector<int> v;
for (int i = 1; i <= n; i++) {
if (a[i] >= i) {continue;}
res += (long long)(lower_bound(v.begin(), v.end(), a[i]) - v.begin());
v.push_back(i);
}
cout << res << '\n';
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int tt; cin >> tt; for (int i = 1; i <= tt; i++) {solve();}
// solve();
}