A. Detective Book
题意：一个人读书 给出每一章埋的坑在第几页可以填完 。 一个人一天如果不填完坑他就会一直看 问几天能把这本书看完
思路：模拟一下 取一下过程中最大的坑的页数 如果最大页数等于当前页数 day++即可
#include<bits/stdc++.h>
using namespace std;
#define FOR(i,f_start,f_end) for(int i=f_start ;i<=f_end;i++)
#define MT(x,i) memset(x,i,sizeof(x))
#define inf 0x3f3f3f3f
#define mkp make_pair
#define all(v) (v).begin(),(v).end()
#define F first
#define S second
#define pii pair<int,int>
#define pb push_back
const int maxn=+;
int a[maxn];
int main(){
int n,k;
scanf("%d",&n);
for(int i=;i<=n;i++)scanf("%d",&a[i]);
int p=,maxnum=;
int cnt=;
while(p<=n){
if(a[p]>=maxnum){
maxnum=a[p];
}
if(p==maxnum){
cnt++;
maxnum=;
}
p++;
}
cout<<cnt<<endl;
return ;
}
B. Good String
题意：给出只含 > <的字符串 >可以免费把右边的字符删掉 <可以免费把左边的字符删掉 越界就什么都没变化 问不免费删几次可以把该字符串全部变成一种字符
思路: 如果s[0]='>'或者s[n]='<'都是可以直接把一边全部免费删掉的 如果不是这两种情况 那么就找 从左边开始 和s[n] 相等 的最小位置 和从右边开始和s[1]相等的最小位置 哪个小输出哪个
#include<bits/stdc++.h>
using namespace std;
#define FOR(i,f_start,f_end) for(int i=f_start ;i<=f_end;i++)
#define MT(x,i) memset(x,i,sizeof(x))
#define inf 0x3f3f3f3f
#define mkp make_pair
#define all(v) (v).begin(),(v).end()
#define F first
#define S second
#define pii pair<int,int>
#define pb push_back
const int maxn=+;
char s[maxn];
int main(){
int t;
int n;
scanf("%d",&t);
while(t--){
scanf("%d",&n);
scanf("%s",s+);
if(s[]!=s[n]){
if(s[]=='<'){
int ans=;
for(int i=n;i>=;i--){
if(s[i]=='<'){
ans=n-i;break;
}
}
for(int i=;i<=n;i++){
if(s[i]=='>'){
ans=min(i-,ans);
break;
}
}
cout<<ans<<endl;
}
else if(s[]=='>'){
cout<<<<endl;
} }
else {
cout<<<<endl;
} }
return ;
}
C. Playlist
题意 给出n个pair 和k 可以选k个以内的Pair 问最大的 min(first)*(sigma(second))是多少
思路“：直接优先队列升序存second 然后按first 降序排列 n个pair 从最大的Pair开始枚举 每次进优先队列 如果队列超过k 就把 second小的出队即可
比赛的时候想复杂了 想成了还要删除一个点 不知道怎么处理重复 其实删除也可以写 用multiset删除的时候只要删除find回的那个位置的值就不会把相同的全部删掉了
#include<bits/stdc++.h>
#define FOR(i,f_start,f_end) for(int i=f_start;i<=f_end;i++)
#define MS(arr,arr_value) memset(arr,arr_value,sizeof(arr))
#define F first
#define S second
#define pii pair<long long ,long long >
#define mkp make_pair
#define pb push_back
using namespace std;
typedef long long ll;
const int maxn=5e6+;
priority_queue<int,vector<int>,greater<int> >q;
pii a[maxn];
bool cmp(pii a,pii b){
return a.S>b.S;
}
int main(){
int n,k;
scanf("%d%d",&n,&k);
int x,y;
for(int i=;i<=n;i++){
scanf("%d%d",&x,&y);
a[i].F=x;a[i].S=y;
}
sort(a+,a++n,cmp);
q.push(a[].F);
long long sum=a[].F;
long long ans=1ll*a[].F*a[].S;
for(int i=;i<=n;i++)
{
q.push({a[i].F});
sum+=a[i].F;
while(q.size()>k){sum-=q.top();q.pop();}
ans=max(ans,sum*a[i].S);
}
cout<<ans<<endl; return ;
}
D. Minimum Triangulation
题意：给出正n边形 分解成很多个不相交的三角形 并且不相交全覆盖正n边形 n边形角编号逆时针 1--n 三角形的权值为三个角编号乘积 问所有三角形最小乘积和是多少
思路：面向样例编程 每个三角形都从1点出发即可（不会证）
#include<bits/stdc++.h>
using namespace std;
#define FOR(i,f_start,f_end) for(int i=f_start ;i<=f_end;i++)
#define MT(x,i) memset(x,i,sizeof(x))
#define inf 0x3f3f3f3f
#define mkp make_pair
#define all(v) (v).begin(),(v).end()
#define F first
#define S second
#define pii pair<int,int>
#define pb push_back
const int maxn=+;
char s[maxn];
int main(){
int n,k;
scanf("%d",&n);
long long ans=;
for(int i=;i<=n-;i++){
ans+=1ll*i*(i+);
}
cout<<ans<<endl; return ;
}
E. Palindrome-less Arrays
题意：给定一串数字 不确定的地方用-1 表示 确定的就有确切的数字 不能有大于1的奇回文串 问在-1的地方填数字 可以填1---k 有多少种填法
思路 ：由不能有大于1的奇回文串 等价于 奇数序号的数字相邻不能相等 偶数序号的数字相邻不能相等 分解出来即可、
然后进行状态定义 dp[i][0/1] 表示i位置和下一个确定数字的数字相同的填法（第二维是1） 和不同的填法（第二维是0）
需要特殊处理开始和结尾 即 ：- 1 -1 -1 -1 A A表示已经确定的数字 开头的可能性为pow(k-1,有多少个1) 结尾类似
其余的确定数字之前的段可以提取出来分段dp 乘法原理乘起来即可
中间转移为 dp[i][1]=dp[i-1][0]
dp[i][0]=dp[i-1][0]*(k-2)+dp[i-1][1]*(k-1)
这里其实就是分类讨论的思想 如果dp只有一维的话那么后面的数字就会影响前面 产生后效性
那么怎么取消这种后效性呢？那就是对后面的数字进行分类讨论 相当于已经确定了后面的数字
所以前面填数字的时候就可以根据分类讨论的类别来进行转移 就可以取消后效性了
#include<bits/stdc++.h>
#define FOR(i,f_start,f_end) for(int i=f_start;i<=f_end;i++)
#define MS(arr,arr_value) memset(arr,arr_value,sizeof(arr))
#define F first
#define S second
#define pii pair<long long ,long long >
#define mkp make_pair
#define pb push_back
using namespace std;
typedef long long ll;
const int maxn=2e5+;
const ll mod=;
long long a[maxn];
long long dp[maxn][];
ll n,k;
vector<ll>even,odd;
vector<ll>even_div,odd_div;
long long solve(const vector<ll>&a,const vector<ll>&div,int flag){
long long ans=;
if(div.size()==){
ans=k;
ans%=mod;
for(int i=;i<a.size();i++){
ans*=(k-);
ans%=mod;
}
return ans;
}
if(div[]!=){
for(int i=;i<div[];i++){
ans*=(k-);
ans%=mod;
}
}
MS(dp,);
for(int z=;z<div.size()-;z++){
//cout<<a[div[z]]<<" what ? "<<a[div[z+1]]<<endl;
if(a[div[z]]!=a[div[z+]]){
dp[div[z]][]=;
dp[div[z]][]=;
}
else dp[div[z]][]=,dp[div[z]][]=;
}
for(int z=;z<div.size();z++){
//int zz=0;
if(a[div[z-]]!=a[div[z]])dp[div[z-]][]=;
for(int i=div[z-]+;i<div[z];i++){
// zz=1;
//if(i!=div[z]-1)dp[i][0]=(((dp[i-1][1]+dp[i-1][0])%mod)*(k-1)%mod);
dp[i][]=(((dp[i-][]*(k-)%mod)+(dp[i-][]*(k-)%mod))%mod);
// cout<<i<<" ?? "<<dp[i-1][0]<<" fuck "<<dp[i-1][1]<<endl;
dp[i][]=dp[i-][]%mod; }
ans=((ans*dp[div[z]-][])%mod);
}
for(int i=div[div.size()-]+;i<a.size();i++){
ans*=(k-);
ans%=mod;
}
//cout<<ans<<endl;
return ans;
}
int main(){
scanf("%lld%lld",&n,&k);
FOR(i,,n)scanf("%lld",&a[i]);
for(int i=;i<=n;i+=){
odd.push_back(a[i]);
}
for(int i=;i<=n;i+=){
even.push_back(a[i]);
}
for(int i=;i<odd.size();i++){
if(odd[i]!=-)odd_div.push_back(i);
if(i!=&&odd[i]==odd[i-]&&odd[i]!=-){
cout<<<<endl;
return ;
} }
for(int i=;i<even.size();i++){
if(i!=&&even[i]==even[i-]&&even[i]!=-){
cout<<<<endl;
return ;
}
if(even[i]!=-)even_div.push_back(i);
}
long long temp1,temp2;
temp1=solve(odd,odd_div,);
temp2=solve(even,even_div,);
cout<<((temp1%mod)*(temp2%mod))%mod<<endl;
return ;
}