598A - Tricky Sum 20171103
$$ans=\frac{n(n+1)}{2} - 2\sum_{k=0}^{\left \lfloor \log_2 n \right \rfloor}{2^{k}}$$
#include<stdlib.h>
#include<stdio.h>
#include<math.h>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
long long t,n,ans;
void init()
{
scanf("%I64d",&n);ans=n*(n+)/;
for(long long i=;i<;i++)if((1ll<<i)<=n)ans-=*(1ll<<i);
printf("%I64d\n",ans);
}
int main()
{
scanf("%I64d",&t);
for(int i=;i<t;i++)init();
return ;
}
598B - Queries on a String 20171103
设t[i]为最终来到位置i的字符的原位置，对每个位置i，倒序遍历每次操作，若有操作区间覆盖到t[i]，则可以找出在这次操作之后来到位置t[i]的字符原来在哪个位置，并更新t[i]
#include<stdlib.h>
#include<stdio.h>
#include<math.h>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
int m,l[],r[],k[],t[];
string s;
int main()
{
cin>>s;
scanf("%d",&m);
for(int i=;i<=m;i++)
scanf("%d%d%d",&l[i],&r[i],&k[i]),l[i]--,r[i]--;
for(int i=;i<s.size();i++)
{
t[i]=i;
for(int j=m;j>=;j--)
if(l[j]<=t[i] && t[i]<=r[j] && l[j]<r[j])
t[i]=(t[i]-l[j]+r[j]-l[j]+-k[j]%(r[j]-l[j]+))%(r[j]-l[j]+)+l[j];
}
for(int i=;i<s.size();i++)printf("%c",s[t[i]]);
return ;
}
598C - Nearest vectors 20171103
对每个坐标对应的辐角进行排序，显然最小的夹角是来自相邻的两项，O(n)扫一遍即可
#include<stdlib.h>
#include<stdio.h>
#include<math.h>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
#define pi acos(-1.0)
struct rua
{
long double angle;
int id;
}a[];
int n,ans1,ans2;long double x,y,m,_;
bool cmp(rua A,rua B){return A.angle<B.angle;}
int main()
{
scanf("%d",&n);
m=;
for(int i=;i<n;i++)
{
cin>>x>>y;
a[i].angle=atan2(y,x);
a[i].id=i;
}
sort(a,a+n,cmp);
for(int i=;i<n;i++)
{
_=a[(i+)%n].angle-a[i].angle;
if(_<)_+=*pi;
if(_<m)m=_,ans1=a[i].id+,ans2=a[(i+)%n].id+;
}
printf("%d %d\n",ans1,ans2);
return ;
}
598D - Igor In the Museum 20171103
简单并查集，预处理每个区域能看到的壁画数量即可
#include<stdlib.h>
#include<stdio.h>
#include<math.h>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
struct rua
{
int x,y;
}fa[][];
int n,m,k,x,y,ans[][];
char s[][];
char read()
{
char 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);
}
int calc(int i,int j)
{
int _=;
_+=s[i-][j]=='*';
_+=s[i+][j]=='*';
_+=s[i][j+]=='*';
_+=s[i][j-]=='*';
return _;
}
int main()
{
scanf("%d%d%d",&n,&m,&k);
for(int i=;i<=n;i++)
for(int j=;j<=m;j++)
s[i][j]=read();
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++)
{
if(s[i][j]=='*')continue;
if(s[i-][j]=='.')Union(i,j,i-,j);
if(s[i][j-]=='.')Union(i,j,i,j-);
}
for(int i=;i<=n;i++)
for(int j=;j<=m;j++)
fa[i][j]=Find(i,j);
for(int i=;i<=n;i++)
for(int j=;j<=m;j++)
if(s[i][j]=='.')
ans[fa[i][j].x][fa[i][j].y]+=calc(i,j);
for(int i=;i<=k;i++)
scanf("%d%d",&x,&y),printf("%d\n",ans[Find(x,y).x][Find(x,y).y]);
return ;
}
598E - Chocolate Bar 20171108
设f[n][m][k]为对应答案，考虑横切竖切的所有情况，记忆化搜索就好了
#include<stdlib.h>
#include<stdio.h>
#include<math.h>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
int T,n,m,k,f[][][];
int dfs(int n,int m,int k)
{
if(k==n*m || f[n][m][k] || !k)return f[n][m][k];
int ans=;
for(int i=;i<=n-i;i++)
for(int j=;j<=k;j++)
ans=min(ans,dfs(i,m,j)+dfs(n-i,m,k-j)+m*m);
for(int i=;i<=m-i;i++)
for(int j=;j<=k;j++)
ans=min(ans,dfs(n,i,j)+dfs(n,m-i,k-j)+n*n);
return f[n][m][k]=ans;
}
int main()
{
scanf("%d",&T);
for(int i=;i<=T;i++)
{
scanf("%d%d%d",&n,&m,&k);
printf("%d\n",dfs(n,m,k));
}
return ;
}
598F - Cut Length 20180831
学长的模板真是好用，在模板下面加了几行就过了_(:з」∠)_
贴个链接 http://zjhl2.is-programmer.com/posts/210807.html
/*
学长的模板
*/
LINE l;
int n,m;
POLYGON rua;
int main()
{
scanf("%d%d",&n,&m);
rua.read(n);
while(m--)
l.read(),printf("%.6lf\n",(double)rua.cutlength(l));
return ;
}