contents

CF EDU 1A Tricky Sum [题目链接](http://codeforces.com/contest/598/problem/A)思路代码 B Queries on a String [题目链接](http://codeforces.com/contest/598/problem/B)思路代码 C Nearest vectors [题目链接](http://codeforces.com/contest/598/problem/C)思路代码实现细节代码 D Igor In the Museum [题目链接](http://codeforces.com/contest/598/problem/D)思路 E Chocolate Bar [题目链接](http://codeforces.com/contest/598/E)思路 F 不会！！！ LYP AK IOI；

CF EDU 1

A Tricky Sum 题目链接

思路

首先如果2的次幂是减号的话， 我们可以将2的次幂这个等比数列求出来。 根据等比数列求和公式$\frac{a1(1-q^n)}{1-q}$， 将公比2代入， 将a1为1 代入， 可得${\sum }_{i=0}^n{2}^i=2^{n+1}-1$。那么， 原题我们就可以将答案减去这个2的次幂和了 再来考虑剩下的： 原题中剩下的都是正的， 为1到n中不是2的次幂和的数之和。根据容斥， 所以剩下的和等于1-n之和减去2的次幂和。 那么答案就等于1-n之和减去两倍的2的次幂和。 1-n之和等于$(1+n)\ast n/2$; 原题得解

代码

#include<bits/stdc++.h> using namespace std; typedef long long ll; ll T,n,ans; int main() { cin >> T; while(T--) { cin >> n,ans=n*(n+1)/2; int x=1; while(x<=n) ans-=2*x,x*=2; printf("%lld\n",ans); } return 0; }

B Queries on a String 题目链接

思路

可以很轻松容易的发现一个操作中奇特的性质。 对于一个区间[l, r], 将它后k个字符放到开头来， 相当于： 在一个区间为[0, r - l]的字符串里， 将[l,r]赋值给这个区间， 然后对于这个新区间`的每个字符，（设下标为i）， 都变换成了（i+k) % (r - l + 1) 原理是因为前面的字符由于尾部的k个字符移到了前面来， 所以前进k； 然而后面的字符加上k后在%(r-l+1)就自动的到了前面了。 注：大佬们都用的rotate函数， 可以参考学习。

代码

#include<bits/stdc++.h> using namespace std; typedef long long ll; ll read(){ ll a=0,b=getchar(),c=1; while(!isdigit(b))c=b=='-'?-1:1,b=getchar(); while(isdigit(b))a=a*10+b-'0',b=getchar(); return a*c; } ll m,l,r,k; string s; int main(){ cin >> s >> m; while(m--){ l=read(),r=read(),k=read(); k%=r-l+1,rotate(&s[l-1],&s[r-k],&s[r]); } cout << s; return 0; } //上面是大佬做法， 下面是蒟蒻做法 #include<bits/stdc++.h> using namespace std; string s; int q,m,l,r,k; char c[10001]; void work(int l,int r,int k) { m=r-l+1; for(int i=l;i<=r;i++) c[(i-l+k)%m]=s[i]; for(int i=l;i<=r;i++) s[i]=c[i-l]; return ; } int main() { cin>>s; scanf("%d",&q); while(q--) { scanf("%d%d%d",&l,&r,&k); work(l-1,r-1,k); } cout<<s; return 0; }

C Nearest vectors 题目链接

思路

首先按照坐标进行极角排序， 如何排呢？ atan2函数：输入坐标（double）y, x， 返回向量(x,y)与x轴的夹角(弧度制)。 容易想到， 一二象限函数值为整， 三四象限函数值为负， 所以此函数值域为$[-\pi ,\pi ]$。 那么根据此函数， 我们可以想到排序后的向量应该是这个样子： 那么对于夹角最小的向量就是相邻两个的向量， 扫一边维护最小值即可。

代码实现细节

首先，有三种情况：两个向量与x轴夹角：1.为负；2.为正； 3.为一正一负； 对于每一个图, 可见两者夹角（中间的圆圈）为p[i+1]的atan2 - p[i]的atan2; 还有， 注意两者夹角如果大于$\pi$的话， 要变成$2\pi$减去当前角； 大佬做法：用vector里面加上一个atan2与向量编号的pair维护

代码

#include<bits/stdc++.h> using namespace std; typedef long long ll; ll read(){ ll a=0,b=getchar(),c=1; while(!isdigit(b))c=b=='-'?-1:1,b=getchar(); while(isdigit(b))a=a*10+b-'0',b=getchar(); return a*c; } vector<pair<long double,int> > a; int n,ansx,ansy; long double sum=1e5; int main(){ n=read(); for(int i=0;i<n;i++){ int x=read(),y=read(); a.push_back({atan2(y,x),i+1}); } sort(a.begin(),a.end()); a.push_back(a[0]); for(int i=0;i<n;i++){ long double x=a[i+1].first-a[i].first; if(x<0)x+=2*acos(-1); if(x<sum)sum=x,ansx=a[i].second,ansy=a[i+1].second; } printf("%d %d",ansx,ansy); return 0; } #include<bits/stdc++.h> //本蒟蒻做法 using namespace std; int n; struct vec { long double x; long double y; long double v; int id; }p[100010]; bool cmp(vec a, vec b) { return a.v < b.v; } int mina; int minb; long double minn = 4.0; int main() { cin >> n; for(int i = 1; i <= n; i++) { long double x, y; cin >> x >> y; p[i].id = i; p[i].x = x; p[i].y = y; p[i].v = atan2(y, x); } sort(p + 1, p + n + 1, cmp); for(int i = 1; i <= n-1; i++) { long double v = p[i+1].v - p[i].v; if(v > acos(-1)) { v = 2 * acos(-1) - v; } if(v < minn) { minn = v; mina = p[i].id; minb = p[i+1].id; } } long double v = p[n].v - p[1].v; if(v > acos(-1)) { v = 2 * acos(-1) - v; } if(v < minn) { minn = v; mina = p[n].id; minb = p[1].id; } cout << mina << " " << minb << endl; return 0; }

D Igor In the Museum 题目链接

思路

这个题实际上一眼就可以看出是搜索。所以只需要把每个联通块儿周围的求出来即可。 真没什么好说的。。。 联通块标个号一累加即可

#include<bits/stdc++.h> using namespace std; const int dx[4] = {0, 1, -1, 0}; const int dy[4] = {1, 0, 0, -1}; int n, m, k; bool mp[1010][1010]; int vis[1010][1010]; int ans[1010 * 1010]; int sum = 0; int cntblocks = 0; int check(int x,int y) { return x>=0&&x<=n&&y>=0&&y<=m; } void dfs(int x, int y) { //cout << x << y; vis[x][y] = cntblocks; //cout << vis[x][y] << endl; for(int i = 0; i < 4; i++) { int nx = x + dx[i]; int ny = y + dy[i]; //cout << nx << " " << ny << endl; if(check(nx, ny) && !vis[nx][ny]) { if(mp[nx][ny] == 1) { // cout << nx << " " << ny << " "; sum++; // printf("ok\n"); } else { dfs(nx, ny); } //cout << endl; } } } int main() { cin >> n >> m >> k; for(int i = 1; i <= n; i++) { for(int j = 1; j <= m; j++) { char c; cin >> c; if(c == '*') { mp[i][j] = 1; } } } while(k--) { int x, y; cin >> x >> y; if(ans[vis[x][y]]) { cout << ans[vis[x][y]] << endl; continue; } cntblocks++; sum = 0; dfs(x, y); ans[cntblocks] = sum; cout << sum << endl; } return 0; }

E Chocolate Bar 题目链接

思路

一看n和m数据范围， 不可能是状压， 由此得出， 一定是高维dp；一顿胡乱操作。 设dp[i][j][k]表示i * j 的巧克力吃掉k块的最小花费 对于任意一块i * j的chocolate， 都有两种切割方式：横着， 竖着。所以我们枚举每一条切割线， 设当前枚举到了切割线c， 假如他是横着的 那么我们的巧克力就被分成了两块：j*c 与 （i - c)*j。那么，将两个的最小花费加起来再加上切割线费用即可。竖着同理， 可切割成i * c与 i * (j-c)两块； 转移方程为:$dp[i][j][k]=min(dp[i-c][j][k-p]+dp[c][j][p]+j\times j，dp[i][j-c][k-p]+dp[i][c][p]+i\times i)$ (p是切下来一块中吃掉的块数） 注意：两个对称的切割线切下来的块数是一样的 所以枚举一半即可。 可以五重循环：i, j, 一共吃掉的块数， 切割线， 切割后其中一块吃掉的块数。 大佬用的记忆化搜索， 将三重循环变量放到递归里枚举， 只枚举切割线长度与切割后其中一块吃掉的块数。这样跑的更快。

#include<bits/stdc++.h> using namespace std; typedef long long ll; ll read(){ ll a=0,b=getchar(),c=1; while(!isdigit(b))c=b=='-'?-1:1,b=getchar(); while(isdigit(b))a=a*10+b-'0',b=getchar(); return a*c; } int T,n,m,k,ans,dp[35][35][55]; int dfs(int x,int y,int z){ if(dp[x][y][z])return dp[x][y][z]; if(x*y==z or z==0)return 0; dp[x][y][z]=1e9; for(int i=1;i<=x-i;i++) for(int j=0;j<=z;j++) dp[x][y][z]=min(dp[x][y][z],dfs(i,y,z-j)+dfs(x-i,y,j)+y*y); for(int i=1;i<=y-i;i++) for(int j=0;j<=z;j++) dp[x][y][z]=min(dp[x][y][z],dfs(x,i,j)+dfs(x,y-i,z-j)+x*x); return dp[x][y][z]; } int main(){ T=read(); while(T--){ n=read(),m=read(),k=read(); printf("%d\n",dfs(n,m,k)); } return 0; } //以下是本菜鸡代码 #include<bits/stdc++.h> using namespace std; long long n, m, k; long long f[60][60][60]; int main() { int t; cin >> t; memset(f, 0x3f, sizeof(f)); //cin >> n >> m >> k; //f[0][0][0] = 0; for(int i = 0; i <= 50; i++) { f[0][0][i] = 0; } for(int i = 1; i <= 30; i++) { for(int j = 1; j <= 30; j++) { if(i * j <= 50) f[i][j][i*j] = 0; f[i][j][0] = 0; } } for(int i = 1; i <= 30; i++) { for(int j = 1; j <= 30; j++) { int p = min(i * j, 50); for(int c = 1; c <= p; c++) { for(int a = 1; a <= i / 2; a++) { int k1 = min(a * j, c); for(int b = 0; b <= k1; b++) f[i][j][c] = min(f[i][j][c], f[i - a][j][c - b] + f[a][j][b] + j * j); } for(int a = 1; a <= j / 2; a++) { int k2 = min(a * i, c); for(int b = 0; b <= k2; b++) { f[i][j][c] = min(f[i][j][c], f[i][a][b] + f[i][j-a][c-b] + i * i); } } } } } while(t--) { int n, m, k; cin >> n >> m >> k; cout << f[n][m][k] << endl; } return 0; }

F 不会！！！

发个题解链接， 是我们机房的一位巨佬， 已经AK IOI了！！ 大佬题解

LYP AK IOI；