比赛链接：https://codeforc.es/contest/1714
这次A了 A题B题C题和E题，开题顺序是CBADE，D题没有什么思路就直接跳了。
div3倒着开题名次提升了不少。这次除了A题有些失误意外其他的都还好。
A题：水题，大意是给出小明睡觉的时间，小时和分钟。给出一堆闹钟，求出在第一个闹钟之前能睡多长时间。
这个题刚开始我是去计算的，结果有些测试点没有过去。因为数据量比较小，所以直接暴力过了。
code：
#include<bits/stdc++.h>
using namespace std;
#pragma GCC optimize(2)
int a[26][65];
int main()
{
ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
int t;
cin>>t;
int n,h,m,x,y;
while(t--)
{
memset(a,0,sizeof a);
cin>>n>>h>>m;
for(int i=1;i<=n;i++)
{
cin>>x>>y;
a[x][y] = 1;
}
int sum = 0;
while(1)
{
if(a[h][m]==1)
{
cout<<sum/60<<' '<<sum%60<<endl;
break;
}
sum++;
m++;
if(m>=60) m%=60,h++;
if(h>=24) h%=24;
}
}
}
B题：大意是给出n个数，然后每次能够删除开头第一个数，求出最少删除多少数能够使得剩下的数互不相同。
解决方法：直接倒着数一遍，直到出现重复。数据量不大可以直接哈希记录，如果数据大可以map做伪哈希。
code：
#include<bits/stdc++.h>
using namespace std;
#pragma GCC optimize(2)
const int nn = 2*1e5+10;
bool sign[nn];
vector<int>ve;
int main()
{
ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
int t;
cin>>t;
while(t--)
{
ve.clear();
memset(sign,false,sizeof sign);
int n,x;
cin>>n;
for(int i=1;i<=n;i++)
{
cin>>x;
ve.push_back(x);
}
int i=ve.size()-1;
for(;i>=0;i--)
{
if(sign[ve[i]]) break;
sign[ve[i]]=true;
}
cout<<i+1<<endl;
}
}
C题：大意是给出一个数字n，求出一个数，这个数由1-9互不相同的数组成，其和为n且最小。
解决方法：从最大的数开始搜，放到最后倒着输出。
code：
#include<bits/stdc++.h>
using namespace std;
#pragma GCC optimize(2)
bool sign[10];
int n;
vector<int>ve;
bool flag;
void dfs(int k,int sum)
{
if(flag == true )
return;
if(sum==n)
{
for(int i=ve.size()-1;i>=0;i--)
cout<<ve[i];
cout<<endl;
flag = true;
return;
}else if(sum>n) return;
for(int i=k;i>=1;i--)
{
ve.push_back(i);
dfs(k-1,sum+i);
ve.pop_back();
}
}
int main()
{
ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
int t;
cin>>t;
while(t--)
{
flag = false;
ve.clear();
cin>>n;
dfs(9,0);
}
}
E题：给出一堆数，每次可以令这些数加上 这个数%10的数。通过不限次数的操作能否使得这些数相等。分情况讨论：如果存在%10==0，则所有的数所达到这个状态且需要相等。否则，任意一个数通过+%10的数可以到达2。例如14-18-26-32 ，13-16-22。要想使得所有数相等，可以让他们到达一个2的状态，从一个2的状态到达另一个2的状态中间相隔20（2-4-8-16-22），求出差距是否是20的倍数。code：
#include<bits/stdc++.h>
using namespace std;
#pragma GCC optimize(2)
#define ll long long
const int nn = 2e5+10;
const int maxn = 1e9+10;
vector<ll>ve;
int main()
{
ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
int t;
cin>>t;
while(t--)
{
ve.clear();
ll n,x;
cin>>n;
for(int i=1;i<=n;i++)
{
cin>>x;
ve.push_back(x);
}
for(int i=0;i<ve.size();i++)
{
while(ve[i]%10!=2&&ve[i]%10!=0)
ve[i]+=ve[i]%10;
}
sort(ve.begin(),ve.end());
if(ve[0]%10==2)
{
int i=0;
for(;i<ve.size()-1;i++)
{
if((ve[i+1]-ve[i])%20!=0)
break;
}
if(i<ve.size()-1)
printf("NO\n");
else
printf("YES\n");
}else
{
int i=0;
for(;i<ve.size()-1;i++)
{
if(ve[i+1]!=ve[i])
break;
}
if(i<ve.size()-1)
printf("NO\n");
else
printf("YES\n");
}
}
}
D题：大意是给出一个字符串，然后给出n个字符串（我们命名为子串）。子串可以无限次使用，求出最少通过多少个子串可以将主串染色。如果不能染色输出-1，否则输出每个子串染色的区间。格式为，子串编号 开始下标。
贪心思想去考虑。因为主串长度不大，我们可以暴力出它的所有子串，然后和n个字符串去比较，将所有的符合条件的子串和位置进行记录。我们可以得到一个段向量。问题变成了在一个段向量中，求出组成一条线的最优方案，这一步可以贪心，复杂度不到n*段数，暴力匹配复杂度n^3,。差不多能过。
code：
#include<bits/stdc++.h>
using namespace std;
#pragma GCC optimize(2)
struct duan{
int str;
int begint;
};
bool cmp(duan a,duan b)
{
return a.begint<b.begint;
}
int main()
{
//ios_base::sync_with_stdio(0); cin.tie(0); //cout.tie(0);
int t;
cin>>t;
while(t--)
{
vector<duan> ve;
vector<duan> ans;
string a;
cin>>a;
int n;
cin>>n;
string z[11];
for(int i=1;i<=n;i++)
cin>>z[i];
for(int k=1;k<=n;k++)
{
for(int i=0;i<a.size();i++)
{
for(int j=1;j<=a.size()-i;j++)
{
if(a.substr(i,j)==z[k])
ve.push_back({k,i});
}
}
}
sort(ve.begin(),ve.end(),cmp);
for(int i=0;i<a.size();)
{
int lasti = i;
int tt = 0, pos = 0;
for(int j=0;j<ve.size();j++)
{
if((ve[j].begint<=i) && (tt==0||ve[j].begint+z[ve[j].str].size()>pos+z[tt].size()))
{
tt = ve[j].str,pos = ve[j].begint;
}
}
i = pos+z[tt].size();
if(tt==0&&pos==0||lasti == i)
{
ans.clear();
break;
}
else
ans.push_back({tt,pos+1});
}
if(ans.size()==0)
cout<<-1<<endl;
else
{
cout<<ans.size()<<endl;
for(int i=0;i<ans.size();i++)
cout<<ans[i].str<<' '<<ans[i].begint<<endl;
}
}
}
Reply