2018.12.28 22：30
看着CF升高的曲线，摸了摸自己的头发，我以为我变强了，直到这一场Edu搞醒了我。。
从即将进入2018年末开始，开启自闭场集合，以纪念(dian)那些丢掉的头发
留坑睡觉。。明天看题解再补
A.Find Divisible
题意：输出[l,r]中满足x|y的x,y，保证有解
思路：直接输出x, 2x即可
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<cstring>
#include<string>
#include<stack>
#include<queue>
#include<deque>
#include<set>
#include<vector>
#include<map>
#include<functional> #define fst first
#define sc second
#define pb push_back
#define mem(a,b) memset(a,b,sizeof(a))
#define lson l,mid,root<<1
#define rson mid+1,r,root<<1|1
#define lc root<<1
#define rc root<<1|1
#define lowbit(x) ((x)&(-x)) using namespace std; typedef double db;
typedef long double ldb;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> PI;
typedef pair<ll,ll> PLL; const db eps = 1e-;
const int mod = 1e9+;
const int maxn = 2e6+;
const int maxm = 2e6+;
const int inf = 0x3f3f3f3f;
const db pi = acos(-1.0); int main() {
int t;
scanf("%d", &t);
while(t--){
ll x, y;
scanf("%lld %lld", &x, &y);
printf("%lld %lld\n", x,*x);
}
return ;
}
B.Substring Removal
题意：删除一个子串，使得剩下的串只有一种字符，问你方案数
思路：分a[1]是否==a[n]两种情况讨论，
等于的时候根据要删除的子串区间端点范围决定方案数
不等于的时候相当于一个端点固定
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<cstring>
#include<string>
#include<stack>
#include<queue>
#include<deque>
#include<set>
#include<vector>
#include<map>
#include<functional> #define fst first
#define sc second
#define pb push_back
#define mem(a,b) memset(a,b,sizeof(a))
#define lson l,mid,root<<1
#define rson mid+1,r,root<<1|1
#define lc root<<1
#define rc root<<1|1
#define lowbit(x) ((x)&(-x)) using namespace std; typedef double db;
typedef long double ldb;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> PI;
typedef pair<ll,ll> PLL; const db eps = 1e-;
const int mod = ;
const int maxn = 2e6+;
const int maxm = 2e6+;
const int inf = 0x3f3f3f3f;
const db pi = acos(-1.0);
char a[maxn];
int main() {
int n;
scanf("%d", &n);
getchar();
scanf("%s", a+);
ll ans = ;
if(a[]==a[n]){
char c = a[];
int l , r;
for(int i = ; i <= n; i++){
if(a[i]!=c){l=i;break;}
}
for(int i = n; i >= ; i--){
if(a[i]!=c){r=i;break;}
}
l = l;
r = n-r+;
ans = 1ll*l*r;
ans%=mod;
}
else{
int l,r;
char c = a[];
for(int i = ; i <= n; i++){
if(a[i]!=c){l=i;break;}
}
c = a[n];
for(int i = n; i >= ; i--){
if(a[i]!=c){r=i;break;}
}
ans = n-r;
ans += l;
ans%=mod;
}
printf("%lld", ans);
return ;
}
C.Polygon for the Angle
题意：问你一个角度最少存在于正几边形中
思路：看代码。。
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<cstring>
#include<string>
#include<stack>
#include<queue>
#include<deque>
#include<set>
#include<vector>
#include<map>
#include<functional> #define fst first
#define sc second
#define pb push_back
#define mem(a,b) memset(a,b,sizeof(a))
#define lson l,mid,root<<1
#define rson mid+1,r,root<<1|1
#define lc root<<1
#define rc root<<1|1
#define lowbit(x) ((x)&(-x)) using namespace std; typedef double db;
typedef long double ldb;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> PI;
typedef pair<ll,ll> PLL; const db eps = 1e-;
const int mod = ;
const int maxn = 2e6+;
const int maxm = 2e6+;
const int inf = 0x3f3f3f3f;
const db pi = acos(-1.0); int main() {
int t;
scanf("%d", &t);
while(t--){
int ag;
scanf("%d", &ag);
int g = __gcd(ag,);
int n = /g;
int m = ag/g;
while(m>n-){n*=;m*=;}
printf("%d\n", n);
}
return ;
}
D.Easy Problem
题意：给你一个字符串，每个字符都有权重，问你删掉多少权重和的字符，使得剩下的字符没有"hard"子序列，并且这个权重和最小
思路：dp[i][j]为前i个字符最多拥有j状态的子序列需要删除的最小权重
其中 j=0代表空，j=1代表"h"，j=2代表"ha"，j=3代表"har"
转移方程在代码里
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<cstring>
#include<string>
#include<stack>
#include<queue>
#include<deque>
#include<set>
#include<vector>
#include<map>
#include<functional> #define fst first
#define sc second
#define pb push_back
#define mem(a,b) memset(a,b,sizeof(a))
#define lson l,mid,root<<1
#define rson mid+1,r,root<<1|1
#define lc root<<1
#define rc root<<1|1
#define lowbit(x) ((x)&(-x)) using namespace std; typedef double db;
typedef long double ldb;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> PI;
typedef pair<ll,ll> PLL; const db eps = 1e-;
const int mod = ;
const int maxn = 2e6+;
const int maxm = 2e6+;
const int inf = 0x3f3f3f3f;
const db pi = acos(-1.0);
char s[maxn];
ll dp[maxn][];
//dp[i][j]表示前i个字符最多有prej作为子序列要删多少
int a[maxn];
int n;
int main() {
scanf("%d", &n);
getchar();
scanf("%s", s+);
for(int i = ; i <= n; i++){
scanf("%d", &a[i]);
}
mem(dp,);
//dp[0][0] = 0;
for(int i = ; i <= n; i++){
for(int j = ; j < ; j++){
dp[i][j] = dp[i-][j];
}
if(s[i]=='h')dp[i][]+=a[i];
if(s[i]=='a')dp[i][]=min(dp[i-][],dp[i][]+a[i]);
if(s[i]=='r')dp[i][]=min(dp[i-][],dp[i][]+a[i]);
if(s[i]=='d')dp[i][]=min(dp[i-][],dp[i][]+a[i]);
}
ll ans = 0x7f7f7f7f7f7f7f7f;
for(int i = ; i <= ;i++){
ans = min(ans, dp[n][i]);
}printf("%lld", ans);
return ;
}