全是真实的比赛代码,思路不明确请原谅。
第一题
事实证明可以getline
。
#include<iostream>
#include<cstdio>
#include<string>
using namespace std;
typedef unsigned int U;
int main() {
freopen("title.in","r",stdin);
freopen("title.out","w",stdout);
ios::sync_with_stdio(false);
string s;
getline(cin,s);
U egg=0;
for(U i=0;i<s.length();i++) {
if(
(s[i]>='A' && s[i]<='Z') ||
(s[i]>='a' && s[i]<='z') ||
(s[i]>='0' && s[i]<='9')
) egg++;
}
cout<<egg<<endl;
return 0;
}
第二题
O(n)
枚举天降神兵位置即可(我都不知道Exile是如何写出O(n²)
的)。
#include<iostream>
#include<cstdio>
using namespace std;
typedef unsigned int U;
typedef unsigned long long ull;
//18446744073709551615
//10000000000000000000
ull c[100100];
int main() {
freopen("fight.in","r",stdin);
freopen("fight.out","w",stdout);
ios::sync_with_stdio(false);
ull n;
cin>>n;
ull f1=0,f2=0;
for(ull i=1;i<=n;i++) {
cin>>c[i];
}
ull m,p1,s1,s2;
cin>>m>>p1>>s1>>s2;
for(ull i=1;i<=n;i++) {
if(i<m) {
f1+=(m-i)*c[i];
}
else if(i>m) {
f2+=(i-m)*c[i];
}
}
if(p1<m) f1+=(m-p1)*s1;
else if(p1>m) f2+=(p1-m)*s1;
ull best1=18446744073709551614ull,egg=-1;
for(ull i=1;i<=n;i++) {
ull ff1=f1,ff2=f2;
if(i<m) ff1+=(m-i)*s2;
else if(i>m) ff2+=(i-m)*s2;
ull diff1=0;
if(ff1>ff2) diff1=ff1-ff2;
else diff1=ff2-ff1;
if(diff1<best1) {
best1=diff1;
egg=i;
}
}
cout<<egg<<endl;
return 0;
}
第三题
具体思路我也不知道...反正AC了(说实话我当时写代码时头昏脑胀)。
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
typedef unsigned int U;
int t[600];
int hash2[4003000];
int suf[4003000];
int tPre[600];
int n,m,maxt;
void boom() {
boom();
}
void printSuffixMap() {
cout<<"Suffix Array: ";
for(int i=0;i<=maxt;i++) {
cout<<suf[i]<<" ";
}
cout<<endl;
}
int _dp[600][50010];
int dp(int x,int tDelta) { //X=Last-Departure-Time
int &ret=_dp[x][tDelta];
if(ret!=-1) return ret;
if(x>=n) {
ret=0;
} else {
if(suf[t[x]+m+tDelta]<=n) {
if(suf[t[x]+m+tDelta]-1 != x) {
int wait=0;
int R=suf[t[x]+m+tDelta];
int L=x+1;
wait=(R-L)*(t[x]+m+tDelta);
wait-=tPre[R-1]-tPre[L-1];
ret=wait+dp(suf[t[x]+m+tDelta]-1,t[x]+m+tDelta-t[suf[t[x]+m+tDelta]-1]);
}
else ret=1429066277;
for(int i=suf[t[x]+m+tDelta];i<=n;i++) {
int wait=0;
int R=i;
int L=x+1;
wait=(R-L)*(t[i]);
wait-=tPre[R-1]-tPre[L-1];
ret=min(ret,wait+dp(i,0));
}
}
else {
int wait=0;
int R=suf[t[x]+m+tDelta];
int L=x+1;
wait=(R-L)*(t[x]+m+tDelta);
wait-=tPre[R-1]-tPre[L-1];
ret=wait;
}
}
return ret;
}
int main() {
freopen("bus.in","r",stdin);
freopen("bus.out","w",stdout);
ios::sync_with_stdio(false);
memset(_dp,255,sizeof(_dp));
cin>>n>>m;
t[0]=-m;
for(int i=1;i<=n;i++) {
cin>>t[i];
if(t[i]+m+10 > maxt) {
maxt=t[i]+m+10;
}
}
sort(t+1,t+1+n);
for(int i=1;i<=n;i++) {
if(hash2[t[i]]<=400) hash2[t[i]]=400+i;
tPre[i]=tPre[i-1]+t[i];
}
int curr=n+1;
for(int j=maxt;j>=0;j--) {
if(hash2[j]>400) curr=hash2[j]-400;
suf[j]=curr;
}
cout<<dp(0,0)<<endl;
//printDpMap();
return 0;
}
第四题
首先,建两棵树,DFS暴力。
为了防止被链状数据卡住,优化是,当一个节点发现其孩子不对称(只有左或只有右)时,直接退出,判为不对称(当时比赛时并没有想到做这个优化,可是歪打正着)。
#include<iostream>
#include<cstdio>
using namespace std;
typedef unsigned int U;
struct node {
int data;
int l,r;
node(){
l=-1;r=-1;
}
}nodes[1000010],rnodes[1000010];
int equalTravel(int o,int r){
if(o==-1 && r==-1) return 0;
if(o==-1 || r==-1) return -1;
if(nodes[o].data != rnodes[r].data) return -1;
int left= equalTravel(nodes[o].l,rnodes[r].l);
int right=equalTravel(nodes[o].r,rnodes[r].r);
if(left==-1 || right==-1) return -1;
else return 1+left+right;
}
int isOK(int x) {
return equalTravel(x,x);
}
int main() {
freopen("tree.in","r",stdin);
freopen("tree.out","w",stdout);
ios::sync_with_stdio(false);
int n;
cin>>n;
for(int i=1;i<=n;i++) {
cin>>nodes[i].data;
rnodes[i].data=nodes[i].data;
}
for(int i=1;i<=n;i++) {
cin>>nodes[i].l>>nodes[i].r;
rnodes[i].r=nodes[i].l;
rnodes[i].l=nodes[i].r;
}
int egg=0;
for(int i=1;i<=n;i++) {
int m=isOK(i);
if(m!=-1) egg=max(egg,m);
}
cout<<egg<<endl;
return 0;
}
你萎啦
#include<bits/stdc++.h>
using namespace std;
int main(){
ios::sync_with_stdio(0);
string s;
int egg=0;
getline(cin,s);
for(int i=0;i<s.length();i++)
if(s[i]!=' ')
egg++;
cout<<egg;
}
你才萎了
垃圾
ntm才垃圾
你是要自由吗?
去吧