转载请注明出处,谢谢 http://blog.csdn.net/ACM_cxlove?viewmode=contents by---cxlove
好可惜的一场,不过凭借一开始的手速,还是涨了rate。
A:LLPS
找出字典序最大的回文子串,显然子串所有字母相同,全为字典序最大的那个,遍历一遍就OK了。
如果中间有别的字母,比如X()()X,括号中是别的小于X的字母,那么这个子串的字典序肯定小于XX
#include<iostream>
#include<iomanip>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cstdlib>
#include<cmath>
#include<map>
#include<set>
#include<queue>
#include<string>
#include<vector>
#define eps 1e-10
#define LL long long
#define LD long double
#define pi acos(-1.0)
using namespace std;
char str[100005];
int main(){
while(scanf("%s",str)!=EOF){
int mmax=0,cnt=0;
for(int i=0;i<strlen(str);i++){
if(str[i]>mmax){
mmax=str[i];
cnt=1;
}
else if(str[i]==mmax)
cnt++;
}
for(int i=0;i<cnt;i++)
printf("%c",mmax);
printf("\n");
}
return 0;
}
B: Brand New Easy Problem
被题目意思卡死,英语差太痛苦了,最后才做,结果还是把逆序对的意思理解错了,没有过system test。太可惜了
有一个字典里包括若干单词,可以任意排列,另外有一些句子,求出两个的相似度,不理解为什么有人直接依次判断就行了,貌似不是最优解啊
因为范围不大,直接全排列,而且在比较的时候我用的是dfs。
#include<iostream>
#include<iomanip>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cstdlib>
#include<cmath>
#include<map>
#include<set>
#include<queue>
#include<string>
#include<vector>
#define eps 1e-10
#define LL long long
#define LD long double
#define pi acos(-1.0)
#define inf 1<<20
using namespace std;
int n,m;
string word[5],tmp[5];
string str[20];
int cnt;
int a[5],x;
int jiecheng(int k){
return k==0?1:k*jiecheng(k-1);
}
int find(string s){
for(int i=0;i<n;i++)
if(s==tmp[i])
return i;
}
void dfs(int pos,int idx){
if(pos==n){
int t=0;
for(int i=0;i<n;i++){
for(int j=i+1;j<n;j++)
if(a[i]>a[j])
t++;
}
x=min(x,t);
return ;
}
for(int j=idx;j<cnt;j++)
if(str[j]==word[pos]){
a[pos]=find(word[pos]);
dfs(pos+1,j+1);
}
}
int main(){
while(cin>>n){
for(int i=0;i<n;i++){
cin>>word[i];
tmp[i]=word[i];
}
int idx=-1,p=0;
cin>>m;
for(int i=1;i<=m;i++){
cin>>cnt;
for(int j=0;j<cnt;j++)
cin>>str[j];
x=inf;
sort(word,word+n);
int ccc=jiecheng(n);
while(ccc--){
next_permutation(word,word+n);
dfs(0,0);
if(n*(n-1)/2-x+1>p){
idx=i;
p=n*(n-1)/2-x+1;
}
}
}
if(idx==-1)
cout<<"Brand new problem!\n";
else{
cout<<idx<<"\n[:";
for(int i=1;i<=p;i++)
cout<<"|";
cout<<":]\n";
}
}
return 0;
}
C:Clear Symmetry
B题开始看不懂,便 很快转战C题,顺序的是很快解决而且1A,完全是靠C题,才涨的rate
枚举1-13,得出解,猜测结论,答案肯定为奇数,而且对于一个奇数i,最多能放i*i/2+1个1,但是要特判n=3,好多人挂在这
#include<iostream>
#include<iomanip>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cstdlib>
#include<cmath>
#include<map>
#include<set>
#include<queue>
#include<string>
#include<vector>
#define eps 1e-10
#define LL long long
#define LD long double
#define pi acos(-1.0)
using namespace std;
int n;
int main(){
while(scanf("%d",&n)!=EOF){
if(n==3)
printf("5\n");
else{
for(int i=1;;i+=2)
if(n<=i*i/2+1){
printf("%d\n",i);
break;
}
}
}
return 0;
}
D - Guess That Car!
把X,Y分开考虑,对于横向的,将中心放在某点上,每一列到中心的横向距离是固定的,便 可以先将横向和纵向和进行预处理。
然后枚举中心点。在计算的时候,我分两两种情况,一种是在左(上)边,一种是在右(下)边,也可以YY出一个综合式子
#include<iostream>
#include<iomanip>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cstdlib>
#include<cmath>
#include<map>
#include<set>
#include<queue>
#include<string>
#include<vector>
#define eps 1e-10
#define LL long long
#define LD long double
#define pi acos(-1.0)
#define inf 1LL<<60
using namespace std;
int c[1000][1000],n,m;
LL col[1000],row[1000];
LL sqr(int x){
return (LL)x*x;
}
int main(){
while(scanf("%d%d",&n,&m)!=EOF){
memset(col,0,sizeof(col));
memset(row,0,sizeof(row));
for(int i=0;i<n;i++)
for(int j=0;j<m;j++){
scanf("%d",&c[i][j]);
row[i]+=c[i][j];
col[j]+=c[i][j];
}
int x=0,y=0;
LL maxx=inf,maxy=inf;
for(int i=0;i<=n;i++){
LL tmp=0;
for(int j=0;j<i;j++)
tmp+=row[j]*sqr((abs(i-j-1)*4+2));
for(int j=i;j<n;j++)
tmp+=row[j]*sqr((abs(j-i)*4+2));
if(tmp<maxx){
x=i;
maxx=tmp;
}
}
for(int i=0;i<=m;i++){
LL tmp=0;
for(int j=0;j<i;j++)
tmp+=col[j]*sqr((abs(i-j-1)*4+2));
for(int j=i;j<m;j++)
tmp+=col[j]*sqr((abs(j-i)*4+2));
if(tmp<maxy){
y=i;
maxy=tmp;
}
}
printf("%I64d\n",maxx+maxy);
printf("%d %d\n",x,y);
}
return 0;
}
E - Fragile Bridges
DP可解。dpl[i][0]表示从i出发遍历0-i的最大值,dpl[i][1]表示从i出发遍历0-i并且回到i的最大值。
dpr[i][0]表示从i出发遍历i-n的最大值,dpr[i][1]表示从i出发遍历i-n并且回到i的最大值。
#include<iostream>
#include<iomanip>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cstdlib>
#include<cmath>
#include<map>
#include<set>
#include<queue>
#include<string>
#include<vector>
#define eps 1e-10
#define LL long long
#define LD long double
#define pi acos(-1.0)
#define inf 1LL<<60
using namespace std;
int a[100000],n;
LL dpl[100000][2],dpr[100000][2];
int main(){
while(scanf("%d",&n)!=EOF){
for(int i=1;i<n;i++)
scanf("%d",&a[i]);
dpl[0][0]=dpl[0][1]=0;
for(int i=1;i<n;i++){
dpl[i][1]=a[i]<=1?0:dpl[i-1][1]+a[i]/2*2;
if(a[i]&1)
dpl[i][0]=dpl[i-1][0]+a[i];
else
dpl[i][0]=max(dpl[i-1][0]+a[i]-1,dpl[i][1]);
}
dpr[n-1][0]=dpr[n-1][1]=0;
for(int i=n-2;i>=0;i--){
dpr[i][1]=a[i+1]<=1?0:dpr[i+1][1]+a[i+1]/2*2;
if(a[i]&1)
dpr[i][0]=dpr[i-1][0]+a[i+1];
else
dpr[i][0]=max(dpr[i][1],dpr[i+1][0]+a[i+1]-1);
}
LL ans=0;
for(int i=0;i<n;i++)
ans=max(ans,max(dpl[i][0],max(dpr[i][0],max(dpl[i][1]+dpr[i][0],dpr[i][1]+dpl[i][0]))));
printf("%I64d\n",ans);
}
return 0;
}
分享到:
相关推荐
Codeforces Round #723 (Div. 2).md
上面代码跑出来的dp[n][m]是0,然后从(1,1)(1,2)(2,2)(2,3)这样的相与值是k (看懂ans+k是啥应该就懂了) 代码: int main() { std::ios::sync_with_stdio(false),cin.tie(0),cout.tie(0); int ans=(1&...
传送门 题意: 开始位置在0,问能否跳到n+1位置 每步只能跳d 在1——n每个位置有方向,L,R,求d的最小值 思路: 只用找相邻两个R之间的最大值即可 代码: #include #include ...typedef long long l
就是把所有相等的数放到一个vector里,如果他出现大于2次,看最远的间距是否大于2即可,找到一个就可以 代码: #include #include #include #include #include #include #include #include #include #include #...
长度为n的字符串包含n−2n−2n−2个aaa和222个bbb,求按照字典序排列输出第kkk个字符串 解题思路 第一个bbb在倒数第二位有1个字符串,在倒数第三位有2个字符串…在倒数第nnn位时有n−1n-1n−1个字符串 可以根据第一...
E. Cyclic Components 题目链接-E. Cyclic Components 题目大意 给你nnn个点和mmm条边,求所构成图中单圈环的个数 ...并查集并查集并查集 很明显单圈环每个点的度都为222,所以我们可以用数组cnt[]记录每个点的度,...
Codeforces Round #629 (Div. 3) E.Tree Queries (DFS) 思路:若ai 在路径上 ,则ai的父结点一定在路径上,若ai是路径上某个结点的子结点,则ai的父结点一定在路径上,综上只需考虑ai的父节点就行了。对每个ai判断...
给两两节点放一个数字(0~n-2 唯一) 给你一棵树,求所有任意两节点相连的路以外的路上的数字的最小值最小 思路 构造 若一个点连了三条边及以上,则这个点的边从最小值开始赋值。其他边从最大点开始赋值。 证明:一...
给一个长度为n的数组,两种操作,一个是把任意一个ai变成ai+2a_i变成a_i+2ai变成ai+2,另一个是如果所有数都大于0,可以把所有数减1,问通过这些操作能否把所有数变为0 思路: 如果任意两个数之差为奇数,那么就...
输入一个正整数x,找出这样的2个正整数a和b,使得gcd(a,b)+lcm(a,b)=x 解题思路 找最特殊的情况a=1,b=x-1即可 这样a,b两个数最大公因数为1,最小公倍数x-1,满足题意√ 附上代码 #include #define int long long #...
B. Longest Palindrome time limit per test1 second memory limit per test256 megabytes inputstandard input outputstandard output Returning back to problem solving, Gildong is now studying about ...
将所有数字看成2进制,从最高位看起,如果第i位上为1的数只有一个的话,那么这个数必然对答案有贡献,就把它排在第一个,后面任意排。 例:11,6,4,0 二进制表示为:1011,110,100,0 右起第四位为1的只有1011,...
C(n-2,i-1)*C(j-1,n-2)*(i-1) __ j: n-1 -> m 我们发现内层循环,每次只是j加一,我们就可以只用一次组合数剩下的用差量表示 对于外层循环同理 只有(i-1) * C(n-2,i-1) i会每次加一。我们也只算一次剩下的用差量...
传说门 刚好今晚是中国场! 其实这道题比较水,但当时思路错,一心想着化简公式,浪费了好多时间a....#pragma GCC optimize(2) #include #define ll long long #define endl '\n' using namespace std; const int manx=
传送门 题意: 找规律,题意就是有多少种方式填充该图形 画两个就发现,输出n即可 代码: #include #include #include #include #include #include #include #include ...#define SZ(x) ((int)(x)
A #include using namespace std; typedef long long ll; int main(){ int t; cin>>t; while(t--){ ll x; cin>>x; cout<<1>>t; while(t--){ st.clear(); ll n; cin >>n;... ll re
题目链接:B. Longest Palindrome 题目 Returning back to problem solving, Gildong is now studying about palindromes. He learned that a palindrome is a string that is the same as its reverse....
惭愧,前几天刚学的dfs序判祖先关系都忘了用。。 这题我们先把所有点都变成父亲节点(根节点不变),这样只需要判所有节点是否在一条链上。 由于判断x是y的祖先:需要满足:st[x]<...const int M = 2e5+