616A - Comparing Two Long Integers 20171121
直接暴力莽就好了...没什么好说的
#include<stdlib.h>
#include<stdio.h>
#include<math.h>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
string a,b;int sa,sb;
char cmp()
{
if(sa==- && sb==-)return '=';
if(sa==-)return '<';if(sb==-)return '>';
if(a.size()-sa>b.size()-sb)return '>';
if(a.size()-sa<b.size()-sb)return '<';
for(int i=sa,j=sb;i<a.size();i++,j++)
if(a[i]!=b[j])return (a[i]<b[j])?'<':'>';
return '=';
}
int main()
{
cin>>a;cin>>b;sa=sb=-;
for(int i=;i<a.size();i++)if(a[i]!=''){sa=i;break;}
for(int i=;i<b.size();i++)if(b[i]!=''){sb=i;break;}
return printf("%c\n",cmp()),;
}
616B - Dinner with Emma 20171121
在每行的最小值中取一个最大值输出就好了
#include<stdlib.h>
#include<stdio.h>
#include<math.h>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
int n,m,x,mi,ans;
int main()
{
scanf("%d%d",&n,&m);
for(int i=;i<=n;i++)
{
mi=;
for(int j=;j<=m;j++)
scanf("%d",&x),mi=min(mi,x);
ans=max(ans,mi);
}
return printf("%d\n",ans),;
}
616C - The Labyrinth 20171121
简单并查集
#include<stdlib.h>
#include<stdio.h>
#include<math.h>
#define N 1150
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
struct rua
{
int x,y;
}fa[N][N];
int n,m,si[N][N];
bool s[N][N];
char ch;
bool read()
{
ch=getchar();
while(ch!='.' && ch!='*')
ch=getchar();
return ch=='.';
}
rua Find(int x,int y)
{
if(fa[x][y].x==x && fa[x][y].y==y)return fa[x][y];
else return fa[x][y]=Find(fa[x][y].x,fa[x][y].y);
}
void Union(int xx,int xy,int yx,int yy)
{
fa[Find(xx,xy).x][Find(xx,xy).y]=Find(yx,yy);
}
bool equal(int xx,int xy,int yx,int yy)
{
return fa[xx][xy].x==fa[yx][yy].x && fa[xx][xy].y==fa[yx][yy].y;
}
int main()
{
scanf("%d%d",&n,&m);
for(int i=;i<=n;i++)
for(int j=;j<=m;j++)
fa[i][j].x=i,fa[i][j].y=j;
for(int i=;i<=n;i++)
for(int j=;j<=m;j++)
{
s[i][j]=read();
if(s[i][j] && s[i-][j])
Union(i,j,i-,j);
if(s[i][j] && s[i][j-])
Union(i,j,i,j-);
}
for(int i=;i<=n;i++)
for(int j=;j<=m;j++)
{
fa[i][j].x=Find(i,j).x;
fa[i][j].y=Find(i,j).y;
si[Find(i,j).x][Find(i,j).y]++;
}
for(int i=;i<=n;i++)
{
for(int j=;j<=m;j++)
if(s[i][j])
printf(".");
else
{
int ans=;
if(s[i-][j])
ans+=si[Find(i-,j).x][Find(i-,j).y];
if(s[i+][j])
if(!equal(i+,j,i-,j))
ans+=si[Find(i+,j).x][Find(i+,j).y];
if(s[i][j-])
if(!equal(i,j-,i-,j))
if(!equal(i,j-,i+,j))
ans+=si[Find(i,j-).x][Find(i,j-).y];
if(s[i][j+])
if(!equal(i,j+,i-,j))
if(!equal(i,j+,i+,j))
if(!equal(i,j+,i,j-))
ans+=si[Find(i,j+).x][Find(i,j+).y];
printf("%d",ans%);
}
printf("\n");
}
return ;
}
616D - Longest k-Good Segment 20171121
先找出当\(l=1\)时\(r\)的最大值，然后O(n)扫一遍。即先增大\(l\)的值到刚好不同元素个数\(<k\)，之后再增大\(r\)的值，这种做法在CF中好像叫做\(two \ pointers\)，在Educational Codeforces Round 50的D题里也有此算法的一个应用
#include<stdlib.h>
#include<stdio.h>
#include<math.h>
#define N 1000001
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
int ansl,ansr,n,k,l,r,s,a[N],b[N];
int main()
{
scanf("%d%d",&n,&k);
for(int i=;i<=n;i++)
scanf("%d",&a[i]);
for(r=;s<=k && r<=n;r++)
s+=(!b[a[r]]),b[a[r]]++;
r--;if(s>k)s--,b[a[r--]]--;
l=ansl=,ansr=r;
while(r<n)
{
for(l;s==k;l++)
b[a[l]]--,s-=(!b[a[l]]);
for(r=r+;s<=k && r<=n;r++)
s+=(!b[a[r]]),b[a[r]]++;
r--;if(s>k)s--,b[a[r--]]--;
if(s==k && ansr-ansl<r-l)
ansr=r,ansl=l;
}
printf("%d %d\n",ansl,ansr);
}
616E - Sum of Remainders 20171121
直接分块做就好了
#include<stdlib.h>
#include<stdio.h>
#include<math.h>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
#define LL long long
#define MOD 1000000007
LL n,m,nexti,ans,an;
LL get_ans(LL a,LL b,LL n)
{
if(n&)an=((n+)/)%MOD*(n%MOD)%MOD;
else an=(n/)%MOD*((n+)%MOD)%MOD;
an*=a%MOD,an%=MOD,an+=(n+)%MOD*(b%MOD)%MOD;
return an%MOD;
}
int main()
{
scanf("%I64d%I64d",&n,&m);
for(LL i=;i<=min(m,n);i=nexti+)
{
nexti=min(m,n/(n/i));
ans+=get_ans(n/i,n%nexti,((n%i)-(n%nexti))/(n/i));
ans%=MOD;
}
if(n<m)ans+=(m-n)%MOD*(n%MOD)%MOD;
printf("%I64d\n",ans%MOD);
return ;
}
616F - Expensive Strings 20180917