Educational Codeforces Round 1
A. Tricky Sum
int fac[N],p2[N];
void init(){
fac[0]=1;p2[0]=1;
for(int i=1;i<=33;i++){
fac[i]=fac[i-1]*2;
p2[i]=p2[i-1]+fac[i];
}
}
void solve(){
int n=read();
int sum=(1+n)*n/2;
cout<<sum-p2[(int)log2(n)]*2<<'\n';
//puts(ans>0?"YES":"NO");
//puts(ans>0?"Yes":"No");
}
B. Queries on a String
void solve(){
string s;
cin>>s;
int n=s.size();
s=' '+s;
// cout<<"chushi:"<<s<<" end"<<'\n';
int q=read();
for(int i=1;i<=q;i++){
int l=read(),r=read(),k=read()%(r-l+1);
string t=" ";
for(int j=1;j<=l-1;j++){
t+=s[j];
}
for(int j=r-k+1;j<=r;j++){
t+=s[j];
}
for(int j=l;j<r-k+1 ;j++){
t+=s[j];
}
for(int j=r+1;j<=n;j++){
t+=s[j];
}
s=t;
// cout<<s<<'\n';
}
for(int i=1;i<=n;i++){
cout<<s[i];
}
//puts(ans>0?"YES":"NO");
//puts(ans>0?"Yes":"No");
}
C. Nearest vectors
极角排序后判断相邻的两个是否是更优
因为有还不会的知识点\(（极角排序）\)所以没写出来
const long double pi=acos(-1);
pair<long double,int> a[N];
void solve(){
int n=read();
for(int i=1;i<=n;i++){
long double x,y;
cin>>x>>y;
long double e=atan2(y,x);
a[i]={e,i};
}
sort(a+1,a+1+n);
a[n+1]=a[1];
long double minn=inf;
int ansx=-1,ansy=-1;
for(int i=1;i<=n;i++){
long double d=fabs(a[i+1].first-a[i].first);
if(d>pi)d=pi*2-d;
if(d<minn){
minn=d;
ansx=a[i].second;
ansy=a[i+1].second;
}
}
cout<<ansx<<" "<<ansy<<"\n";
//puts(ans>0?"YES":"aNO");
//puts(ans>0?"Yes":"No");
}
D. Igor In the Museum
int ans[N][N],vis[N][N],n,m;
char a[N][N];
void bfs(int xx,int yy){
queue<PII>q;
q.push({xx,yy});
vis[xx][yy]=1;
int res=0;
while(q.size()){
int x=q.front().first,y=q.front().second;
q.pop();
if(a[x+1][y]=='.'&&vis[x+1][y]==0)q.push({x+1,y}),vis[x+1][y]=1;;
if(a[x-1][y]=='.'&&vis[x-1][y]==0)q.push({x-1,y}),vis[x-1][y]=1;;
if(a[x][y+1]=='.'&&vis[x][y+1]==0)q.push({x,y+1}),vis[x][y+1]=1;;
if(a[x][y-1]=='.'&&vis[x][y-1]==0)q.push({x,y-1}),vis[x][y-1]=1;;
if(a[x+1][y]=='*')res++;
if(a[x-1][y]=='*')res++;
if(a[x][y+1]=='*')res++;
if(a[x][y-1]=='*')res++;
}
q.push({xx,yy});
ans[xx][yy]=res;
while(q.size()){
int x=q.front().first,y=q.front().second;
q.pop();
if(a[x+1][y]=='.'&&ans[x+1][y]==0)q.push({x+1,y}),ans[x+1][y]=res;
if(a[x-1][y]=='.'&&ans[x-1][y]==0)q.push({x-1,y}),ans[x-1][y]=res;
if(a[x][y+1]=='.'&&ans[x][y+1]==0)q.push({x,y+1}),ans[x][y+1]=res;
if(a[x][y-1]=='.'&&ans[x][y-1]==0)q.push({x,y-1}),ans[x][y-1]=res;
}
}
void solve(){
n=read(),m=read();
int q=read();
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
cin>>a[i][j];
}
}
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
if(ans[i][j]==0&&a[i][j]=='.')bfs(i,j);
}
}
for(int i=1;i<=q;i++){
int x=read(),y=read();
cout<<ans[x][y]<<'\n';
}
//puts(ans>0?"YES":"NO");
//puts(ans>0?"Yes":"No");
}
E. Chocolate Bar
记忆化搜索，用\(F[i][j][ned]\)分别表示，从\(i*j\)的矩形切出\(ned\)个巧克力的消耗
对于每个矩形只有横着掰和竖着掰
让我想起上一场\(div3\)的记忆化搜索也差点没写出来
int f[35][35][55];
int dfs(int n,int m,int ned){
if(n*m==ned||ned==0)return f[n][m][ned]=0;
if(n>m)swap(n,m);
if(f[n][m][ned]){
return f[n][m][ned];
}
int minn=inf;
for(int i=1;i<=n/2;i++){
for(int j=0;j<=ned;j++){
minn=min(minn,m*m+dfs(i,m,j)+dfs(n-i,m,ned-j));
}
}
for(int i=1;i<=m/2;i++){
for(int j=0;j<=ned;j++){
minn=min(minn,n*n+dfs(n,i,j)+dfs(n,m-i,ned-j));
}
}
return f[n][m][ned]=minn;
}
void solve(){
int n=read();
for(int i=1;i<=n;i++){
int x=read(),y=read(),ned=read();
if(x>y)swap(x,y);
dfs(x,y,ned);
cout<<f[x][y][ned]<<'\n';
}
//puts(ans>0?"YES":"NO");
//puts(ans>0?"Yes":"No");
}
F. Cut Length
*2900 计算几何