A. Shortest Path with Obstacle
題意：給出三個點坐标A，B，C，求在不經過C點的條件下，A->B的最短路徑長度
思路：如果C在AB之間則需要繞開C走一個哈曼頓距離+2。其他的情況直接走一個AB的哈曼頓距離。
#include <algorithm>
#include <cstring>
#include <iostream>
using namespace std;
const int N = 1100;
typedef long long LL;
#define long long int;
signed main()
{
int t;
cin>>t;
while(t--)
{
int xx,yy,xf,yf,xb,yb;
cin>>xx>>yy>>xb>>yb>>xf>>yf;
if((xf==xx&&yf==yy)||(xf==xb&&yf==yb)){cout<<0<<endl;continue;}
if((xx==xb&&xx==xf&&((yf-yy)*(yf-yb)<0))||(yy==yb&&yy==yf&&((xf-xx)*(xf-xb)<0)))
{
cout<<abs(xb-xx)+abs(yb-yy)+2;
}
else cout<<abs(xb-xx)+abs(yb-yy);
puts("");
}
}
判共線寫短一些：
B. Alphabetical Strings
題意：給定一個字元串，從a開始按字典序擴充字元串。要麼把下一個字母加到目前字母的相鄰位置，要麼加到字元串的另一端。
思路：定義一個持續增長的字母s。從a的兩側周遊，要麼左邊的等于s,要麼右邊的等于s，找不到s就不合法。
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
int n,m;
int main()
{
int t;
cin>>t;
while(t--)
{
string st;
cin>>st;
n=st.size();
int cnt=0,k=-1;
for(int i=0;i<n;i++)
{
if(st[i]=='a') k=i;
}
char s='b';
int i=k-1;int j=k+1;
while(true)
{
if(st[i]==s)
{
i--;
s++;//char類型++實作字母++；
}
else if(st[j]==s)
{
j++;
s++;
}
else break;
}
if(i==-1&&j==n) cout<<"YES"<<endl;
else cout<<"NO"<<endl;
}
}
C - Pair Programming
題意：一個文本，初始有k行，兩個人A,B，各自有n,m次操作x，當x==0時添加一行，當x>0時，改變第x行，并且隻能一個接一個進行操作，求一個合法操作序列。
思路：這個題顯然不合法一定是來自改變x行但文本行數不夠。同時周遊兩個數組，當周遊到第 i 分鐘時，有0先放0，誰小先放誰，因為先放小的風險小，而且下一次的操作還可能周遊到0。這裡是貪心思想。如果最後兩個數都比文本的行數大就無法操作，直接break。
#include<bits/stdc++.h>
using namespace std;
int n, m, k;
int a[310], b[310];
int main() {
int t;
scanf("%d", &t);
getchar();
while (t--) {
queue<int> q;
scanf("%d %d %d", &k, &n, &m);
for (int i = 1; i <= n; i++)
scanf("%d", &a[i]);
for (int i = 1; i <= m; i++)
scanf("%d", &b[i]);
int i = 1, j = 1;
bool st = true;
while (i + j != n + m + 2) {
if (i <= n && a[i] == 0) {
q.push(0);
i++;
k++;
continue;
}
if (j <= m && b[j] == 0) {
q.push(0);
j++;
k++;
continue;
}
if (i <= n && a[i] <= k) {
q.push(a[i]);
i++;
continue;
}
if (j <= m && b[j] <= k) {
q.push(b[j]);
j++;
continue;
}
st = false;
break;
}
if (st) {
while (!q.empty()) {
int t = q.front();
q.pop();
printf("%d ", t);
}
printf("\n");
} else
printf("-1\n");
}
return 0;
}
D. Co-growing Sequence
題意：給出數字序列A，求數字序列B，滿足①：字典序最小，②：C = A^B，其中C[i] & C[i-1] = C[i]
思路：如果c[i] & c[i + 1] == c[i], 則表明c[i]二進制位為1的位置, c[i + 1]在該位上也要為1。
c[i+1]=a[i + 1] ⊕ b[i + 1]。
由此可見當對應二進制位c[i]為1時，根據^運算性質——b[i+1]要跟a[i+1]不同——即前1後0，前0後1才可以使得 c[i] & c[i + 1] == c[i]成立。
是以我們可以看題目給的a[i+1]對應二進制位是0還是1，從小到大枚舉b[i+1]~2^n，一定滿足字典序。
#include<iostream>
#include<algorithm>
#include<cstring>
#define ll long long
using namespace std;
ll a[200005],b[200005];
int main()
{
int t;
scanf("%d",&t);
while(t--)
{
int n;
scanf("%d",&n);
memset(b,0,sizeof(b));
for(int i=1;i<=n;i++)
{
scanf("%lld",&a[i]);
}
for(int i=2;i<=n;i++)
{
for(int j=30;j>=0;j--)
{
if((a[i-1]^b[i-1])>>j&1)//如果c[i]對應二進制位是1
{
if(!(a[i]>>j&1))//如果是0，則b對應二進制位必須是1
{//如果是1，則b對應二進制位是0是以不需要加2^i
b[i]+=(1<<j);
}
}
}
}
for(int i=1;i<=n;i++)
{
printf("%lld ",b[i]);
}
printf("\n");
}
}
E. Air Conditioners
題意：n個方格橫向排列，k個空調，每個空調有一個溫度，假設空調分布在第 i 個位置，則第 j 個方格的溫度計算公式 t + |i - j|；求這n個方格的溫度分别為多少。
思路：分析可知每個格子的溫度會被很多空調影響，枚舉每個空調的溫度是枚舉不完的。是以對于空白格，它的溫度要麼是被左邊一個影響+1要麼被右邊一個影響+1。對于空調格，它的溫度要麼是被左邊一個影響+1要麼被右邊一個影響+1，要麼是自己的空調溫度。在這些影響裡取最小值，就可以轉化成一個線性Dp問題。
#include<iostream>
#include<algorithm>
#include<cstring>
#define ll long long
using namespace std;
ll a[3000005],t[3000005];
int n,k,m;
int main()
{
cin >> m;
while(m --)
{
cin >> n >> k;
for(int i = 0;i <= n + 1;i ++) t[i] = 100000000000;
for(int i = 1;i <= k;i ++) cin >> a[i];
for(int i = 1;i <= k;i ++)
{
ll x;
cin >> x;
t[a[i]] = x;//有空調的先把空調溫度讀取進去
}
for(int i = 1;i <= n;i ++) t[i] = min(t[i],t[i - 1] + 1);
for(int i = n;i >= 1;i --) t[i] = min(t[i],t[i + 1] + 1);
for(int i = 1;i <= n;i ++) cout << t[i] << " ";
puts("");
}
}