site:http://bailian.openjudge.cn/xly2018/
1、计算任意两天之间的天数
思路：以0为起始点计算天数，然后相减即可。这样的编码复杂度会减少很多。
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
bool isleapyear(int y){
return (y%==&&y%!=||y%==);
}
int sum1(int a1,int b1,int c1){
int md[]={,,,,,,,,,,,,};
int res=a1*;
res+=(a1-)/+;
res-=(a1-)/+;
res+=(a1-)/+;
for(int i=;i<b1;i++)res+=md[i];
if(b1>&&isleapyear(a1)) res++;
res+=c1;
return res;
}
int cnt(int a1,int b1,int c1,int a2,int b2,int c2){
int res1=sum1(a1,b1,c1);
int res2=sum1(a2,b2,c2);
int ans=res2-res1;
return ans;
}
int main(){
int a1,b1,c1,a2,b2,c2;
cin>>a1>>b1>>c1>>a2>>b2>>c2;
printf("%d\n",cnt(a1,b1,c1,a2,b2,c2));
return ;
}
2、回文子串
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int main(){
int n;
cin>>n;
while(n--){
string s;
cin>>s;
int res=;
int residx=;
int length=;
for(int i=;i<s.size();i++){
int j=;
for(;;j++){
if(i-j<||i+j>=s.size()) break;
if(s[i-j]!=s[i+j]) break;
}
j--;
if(*j+>res){
res=*j+;
residx=i;
length=j;
}
}
for(int i=residx-length;i<=residx+length;i++){
printf("%c",s[i]);
}
printf("\n");
}
}
3、归并排序
#include<bits/stdc++.h>
#define maxn 50000
#define inf 0x3f3f3f3f
using namespace std;
typedef long long ll;
int L[maxn],R[maxn],a[maxn],n;
void merge(int l,int mid,int r){
int n1=mid-l,n2=r-mid;
for(int i=;i<n1;i++) L[i]=a[l+i];
for(int i=;i<n2;i++) R[i]=a[mid+i];
L[n1]=R[n2]=inf;
int i=,j=;
for(int k=l;k<r;k++){
if(L[i]<=R[j]) a[k]=L[i++];
else a[k]=R[j++];
}
}
void mergesort(int l,int r){
if(l+<r){
int mid=(l+r)/;
mergesort(l,mid);
mergesort(mid,r);
merge(l,mid,r);
}
}
int main(){
cin>>n;
for(int i=;i<n;i++) cin>>a[i];
mergesort(,n);
for(int i=;i<n;i++){
printf("%d ",a[i]);
}
}
第二种归并排序的写法：
#include<bits/stdc++.h>
#define maxn 50000
#define inf 0x3f3f3f3f
using namespace std;
typedef long long ll;
int tmp[maxn],a[maxn],n;
ll cnt=;
void merge(int l,int m,int r){
int i=l,j=m+,k=;
while(i<=m&&j<=r){
if(a[i]<=a[j]) tmp[k++]=a[i++];
else tmp[k++]=a[j++];
}
while(i<=m) tmp[k++]=a[i++];
while(j<=r) tmp[k++]=a[j++];
for(int i=l;i<=r;i++) a[i]=tmp[i-l];
}
void mergesort(int l,int r){
if(l<r){
int mid=(l+r)>>;
mergesort(l,mid);
mergesort(mid+,r);
merge(l,mid,r);
}
}
int main(){
cin>>n;
for(int i=;i<n;i++) cin>>a[i];
mergesort(,n-);
for(int i=;i<n;i++){
printf("%d ",a[i]);
}
//printf("%d\n",cnt);
}
求逆序对个数：
#include<bits/stdc++.h>
#define maxn 50000
#define inf 0x3f3f3f3f
using namespace std;
typedef long long ll;
int tmp[maxn],a[maxn],n;
ll cnt=; void merge(int l,int m,int r){
int i=l,j=m+,k=;
while(i<=m&&j<=r){
if(a[i]<=a[j]) tmp[k++]=a[i++];
else tmp[k++]=a[j++],cnt+=m-i+;
}
while(i<=m) tmp[k++]=a[i++];
while(j<=r) tmp[k++]=a[j++];
for(int i=l;i<=r;i++) a[i]=tmp[i-l];
} void mergesort(int l,int r){
if(l<r){
int mid=(l+r)>>;
mergesort(l,mid);
mergesort(mid+,r);
merge(l,mid,r);
}
}
int main(){
cin>>n;
for(int i=;i<n;i++) cin>>a[i];
mergesort(,n-);
/*for(int i=0;i<n;i++){
printf("%d ",a[i]);
}*/
printf("%d\n",cnt);
}
2012年thu机试第二题：贪心或dp
#include<bits/stdc++.h>
#define maxn 10006
using namespace std;
typedef long long ll;
int a[maxn];
int main(){
int n,sum=;
cin>>n;
for(int i=;i<n;i++) cin>>a[i],sum+=a[i];
int ave=sum/n;
int store=,ans=,tmp;
for(int i=;i<n;i++){
tmp=a[i]-ave;
store+=tmp;
ans+=abs(store);
}
printf("%d\n",ans);
return ;
}
thu2016第一题：
#include<bits/stdc++.h>
#define maxn 100006
#define inf 0x3f3f3f3f
using namespace std;
typedef long long ll;
int n,m,k,tmp[maxn];
struct node{
int num;
int idx;
}a[maxn];
bool cmp(node &a,node &b){
return (a.num<b.num)||(a.num==b.num&&a.idx<b.idx);
}
bool check(int x){
// printf("%d:\n",x);
int num=;
for(int i=;i<=n;i++){
if(a[i].idx<=x){
tmp[num++]=a[i].num;
}
} if(num<m) return false;
for(int i=;m+i-<num;i++){
if(a[m+i-].num-a[i].num<=k) return true;
}
return false;
} int erfen(int l,int r){
while(l<r){
int mid=(l+r)>>;
if(check(mid)) r=mid;
else l=mid+;
}
return l;
}
int main(){
cin>>n>>m>>k;
for(int i=;i<=n;i++) cin>>a[i].num,a[i].idx=i;
sort(a+,a+n+,cmp);
//for(int i=1;i<=n;i++) printf("%d ",a[i].num);
int ans=erfen(,n+);
if(ans==n+){
printf("impossible\n");
}
else printf("%d\n",ans);
return ;
}
/*
6 3 5
170 169 175 171 180 175
*/
/*
6 4 5
170 169 175 171 180 175
6 5 5
170 169 175 171 180 175
*/
一定会有大模拟。。。
url大模拟：
#include<bits/stdc++.h>
#define maxn 10006
using namespace std;
typedef long long ll;
string s[maxn],t[maxn],tmps;
bool match(string s,string t,bool flag){
int lens=s.size(),lent=t.size();
int ps=,pt=;
while(ps<lens&&pt<lent){
if(s[ps]==t[pt]){
ps++,pt++;
}else{
if(t[pt++]!='<') return false;
if(flag) cout<<" ";
if(t[pt]=='i'){
bool ok=false;
while(s[ps]&&isdigit(s[ps])){
if(s[ps]!='') ok=true;
if(flag&&ok) cout<<s[ps];
ps++;
}
if(!ok) return false;
pt+=;
}else if(t[pt]=='s'){
bool ok=false;
while(s[ps]&&s[ps]!='/'){
ok=true;
if(flag) cout<<s[ps];
ps++;
}
if(!ok) return false;
pt+=;
}else if(t[pt]=='p'){
if(flag){
while(s[ps]) cout<<s[ps],ps++;
}
return true;
}
}
}
return ps==lens&&pt==lent;
}
int main(){
int n,m;
cin>>n>>m;
for(int i=;i<n;i++) cin>>s[i]>>t[i];
for(int i=;i<m;i++){
cin>>tmps;
bool f1=false;
for(int j=;!f1&&j<n;j++){
if(match(tmps,s[j],false)){
cout<<t[j]<<" ";
f1=true;
match(tmps,s[j],true);
}
}
if(!f1) cout<<"";
cout<<"\n";
}
return ;
}
ccf-csp第三题：
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
string text,line;
void solve(){
int l1=text.find("_");
while(l1!=string::npos){
text.replace(l1,,"<em>");
int r1=text.find("_",l1);
text.replace(r1,,"</em>");
l1=text.find("_",r1);
} l1=text.find("[");
while(l1!=string::npos){
int r1=text.find("]",l1);
int l2=text.find("(",r1);
int r2=text.find(")",l2);
string tmp1=text.substr(l1+,r1-l1-);
string tmp2=text.substr(l2+,r2-l2-);
string tt="<a href=\""+tmp2+"\">"+tmp1+"</a>";
text.replace(l1,r2-l1+,tt);
l1=text.find("[",r2);
} //主要分为三部分
if(text[]=='#'){
int i=;
while(text[i]=='#') i++;
text="<h"+string(,''+i)+">"+text.substr(i+,text.size()-i-)+"</h"+string(,''+i)+">\n";
}else if(text[]=='*'){
text.insert(,"<ul>\n");
text.insert(text.size(),"</ul>\n");
l1=text.find("*");
while(l1!=string::npos){
text.replace(l1,,"<li>");
int r1=text.find("\n",l1);
text.insert(r1,"</li>");
l1=text.find("*",r1);
}
}else{
text="<p>"+text.substr(,text.size()-)+"</p>\n";
}
cout<<text;
text="";
}
int main(){
freopen("C:\\Users\\Administrator\\Desktop\\demo2047.txt","r",stdin);
text="";
while(getline(cin,line)){
if(line.size()>) text+=line+"\n";
else if(line.size()==&&text.size()>) solve();
}
if(text.size()>) solve();
return ;
}