最失败的一集。
C
开题顺序搞错，不小心先开了C，以为是A。还好C不难。
题意大概是在给定的数组最后添一个数（所有数两两不同），再自定义一个数 \(k\) ，数组中每个数可以加上若干个 \(k\) ，最后使得所有数字相等。要求加 \(k\)
的次数最少。
如果不加最后一个数，那么显然把所有的数加到与最大的那一个数相等最优，\(k\) 就是所有数与最大值的差的 \(\gcd\) 。
考虑加上最后一个数：
假设最后一个数不是最大值，那么只要让它与最大值的差值最小且这个差值是 \(k\) 的倍数。可以直接枚举 \(1\) 到 \(n\) 每个 \(k\) 的倍数是否出现过。最劣的情况差为 \(nk\) ，答案 \(+n\)。
假设最后一个数是最大值，那么其他每个数都要加一次 \(k\) ，答案 \(+n\) 这和以上那种情况中最劣的相同，可以不考虑。
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e6+5,MOD=998244353;
int gcd(int x,int y)
{
return y?gcd(y,x%y):x;
}
signed main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int T;cin>>T;
while(T--)
{
int n;cin>>n;
vector<int> A(n);
for(int i=0;i<n;i++) cin>>A[i];
sort(A.begin(),A.end());
if(n==1) cout<<1<<endl;
else
{
int g=A[1]-A[0],ans=0;
for(int i=2;i<n;i++)
g=gcd(g,A[i]-A[i-1]);
map<int,int> mp;
for(int i=0;i<n;i++) ans+=(A[n-1]-A[i])/g,mp[(A[n-1]-A[i])/g]++;
for(int i=1;i<=n;i++) if(!mp[i])
{
ans+=i;
break;
}
cout<<ans<<endl;
}
}
}
A
签到题，给一个01串，可以再01或10之间插入0，可以在00或11之间插入1，问最终能否使0的个数多于1。
只要不是全1就可以。
B
细节题。给定 \(n,P,l,t\) ，\(n\) 是总天数，\(P\) 是 \(n\) 天内要拿的分，\(l\) 是上一节课的分数，\(t\) 是做一次作业的分数。
一天做多做两次作业，上一节课。并且作业只会在第 \((1+7*k)\) 天布置一次，可以再布置之后的任意一天做。
问做多能休息几天，也就是最小化做作业和上课的天数。
一开始的想法是二分答案，但写完之后发现会爆 long long 。所以不行。
其实只要分类讨论，显然把所有作业放到最后几天完成最优（符合实际），并且做作业的几天去上课显然不亏。
于是判断最后几天做完作业并且在那几天去上课能否满足 \(P\) 分要求，满足则再看能否少上几天，不满足就用上课填余下的分数。
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e6+5,MOD=998244353;
int n,P,l,t,ans;
signed main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int T;cin>>T;
while(T--)
{
cin>>n>>P>>l>>t;
int tasks=(n-1)/7+1;
if(tasks*t+(tasks+1)/2*l>=P)
{
cout<<n-(P+2*t+l-1)/(2*t+l)<<endl;
}
else
{
P-=tasks*t+(tasks+1)/2*l;
n-=(tasks+1)/2;
cout<<n-(P+l-1)/l<<endl;
}
}
}
好了，后面都是我没敲出来题了。但是思想不难，可做。
但为什么放三道数据结构？
D
题意：机器人按照给出的包含UDRL的字符串从 \((0,0)\) 开始行动，\(q\) 个询问包含 \(l,r,x,y\) ，问翻转行动序列的从 \(l\) 到 \(r\) 的子串，机器人是否经过点 \((x,y)\) 。
首先可以预处理整条路线，翻转一段行动序列就是把图形局部旋转 \(180°\) 。但路线旋转 \(180°\) 不好维护，于是想到可以旋转每个询问的点，这样就不用对序列进行操作。
于是可以维护每一个经过的点被机器人经过的所有时间，用这些时间与每个询问的 \(l,r\) 作比较，可以得到答案。
#include<bits/stdc++.h>
// #define int long long
using namespace std;
const int N=2e5+5,MOD=998244353;
template<class T>inline void read(T &x)
{
x=0;int f=0;char ch=getchar();
while(!isdigit(ch)) f=ch=='-',ch=getchar();
while(isdigit(ch)) x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
x=f?-x:x;
}
template<class T>inline void write(T x)
{
if(x<0) return putchar('-'),write(-x);
if(x>9) write(x/10);
putchar('0'+x%10);
}
#define trans(x,y) ((x+n)*(2*n+1)+(y+n))
int p[N];
unordered_map<int,vector<int>> mp;
pair<int,int> poi[N];
pair<int,int> rotate(pair<int,int> A,pair<int,int> O)
{
return make_pair(O.first-A.first,O.second-A.second);
}
pair<int,int> operator + (const pair<int,int> x,const pair<int,int> y)
{
return make_pair(x.first+y.first,x.second+y.second);
}
signed main()
{
int n,q;
read(n),read(q);
poi[0]=make_pair(0,0);
p[0]=trans(0,0);
mp[p[0]].push_back(0);
for(int i=1,x=0,y=0;i<=n;i++)
{
char c=getchar();
while(c!='U'&&c!='D'&&c!='R'&&c!='L') c=getchar();
if(c=='U') y++;
if(c=='D') y--;
if(c=='R') x++;
if(c=='L') x--;
poi[i]=make_pair(x,y);
// cout<<poi[i+1].first<<','<<poi[i+1].second<<endl;
p[i]=trans(x,y);
mp[p[i]].push_back(i);
}
while(q--)
{
int x,y,l,r,fl=0,id,id_ro;
cin>>x>>y>>l>>r;
pair<int,int> now=make_pair(x,y);
pair<int,int> now_ro=rotate(now,poi[l-1]+poi[r]);
id=trans(now.first,now.second),id_ro=trans(now_ro.first,now_ro.second);
#define tmp mp[id]
#define tmp_ro mp[id_ro]
// vector<int> tmp=mp[trans(now.first,now.second)];
// vector<int> tmp_ro=mp[trans(now_ro.first,now_ro.second)]; //vector 赋值复杂度就萎了
if(!tmp.empty())
{
if(tmp[0]<l||tmp[tmp.size()-1]>=r) fl=1;
}
if(!tmp_ro.empty())
{
int pos=lower_bound(tmp_ro.begin(),tmp_ro.end(),l)-tmp_ro.begin();
if(pos<tmp_ro.size()&&tmp_ro[pos]<r) fl=1;
}
if(fl) puts("YES");
else puts("NO");
}
}
E
题意：若 \(A\)、\(B\) 是字符串，
\[C(A,B)=
\begin{cases}
C(A_{2,n},B_{1,n-1}),\,\,A_1=B_n\\
A+B,\,\,\text{otherwise}\\
\end{cases}
\]
给定 \(n\) 个字符串求：
\[\sum_{i=1}^{n}\sum_{j=1}^{n}C(s_i,s_j)
\]
trie树裸题，每次把一个串丢进trie中统计一次答案，再将串反向插入trie。
但必须反着再做一次，还要加上每个串自己与自己匹配的贡献。
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N=1e6+5,MOD=998244353;
string S[N];
struct node{
int son[26];
ll num,cnt;
}trie[N];
int n,rt,tot;
ll ans;
string s;
void insert(int &id,int pos)
{
if(!id) id=++tot;
trie[id].cnt++;
trie[id].num+=s.size()-pos;
if(pos>=s.size()) return;
insert(trie[id].son[s[pos]-'a'],pos+1);
}
void query(int id,int pos)
{
if(!id) return;
int Son=trie[id].son[s[pos]-'a'];
if(pos==s.size()-1)
{
ans+=trie[id].num-(trie[Son].num+trie[Son].cnt)+(trie[id].cnt-trie[Son].cnt)+trie[Son].num;
// cout<<ans<<" : "<<trie[id].num<<" "<<(trie[Son].num+trie[Son].cnt)<<" " <<(trie[id].cnt-trie[Son].cnt)<<" "<<trie[Son].num-trie[Son].cnt<<endl;
return;
}
ans+=trie[id].num-(trie[Son].num+trie[Son].cnt)+(s.size()-pos)*(trie[id].cnt-trie[Son].cnt);
// cout<<Son<<" "<<trie[id].num<<" "<<(trie[Son].num+trie[Son].cnt)<<" " <<(s.size()-pos)*(trie[id].cnt-trie[Son].cnt)<<endl;
query(Son,pos+1);
}
void solve()
{
query(rt,0);
// cout<<s<<"?"<<ans<<endl;
reverse(s.begin(),s.end());
insert(rt,0);
}
void cul(string s)
{
for(int i=0;i<s.size();i++)
if(s[i]!=s[s.size()-i-1])
{
ans+=2*(s.size()-i);
break;
}
}
signed main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
cin>>n;
for(int i=1;i<=n;i++)
cin>>S[i],cul(S[i]);
for(int i=1;i<=n;i++) s=S[i],solve();
memset(trie,0,sizeof(trie));
rt=tot=0;
for(int i=n;i;i--) s=S[i],solve();
cout<<ans<<endl;
}
F
还没写完，先咕着。
- Educational Codeforces Round 159educational codeforces round 159 educational codeforces round rated educational codeforces round 151 construction educational codeforces round educational codeforces round 147 cf-educational educational codeforces round educational codeforces round 158 educational codeforces contest round educational codeforces monsters round educational codeforces balance round