第一題 987654321 problem
水題，打個表找個規律，一瞬間就好了。。
#include
#include
using namespace std;
int main()
{
/*for(long long i=1000;i<=0x7ffffffff;i++)
{
if((i*i)%1000000000==987654321)
{
cout<>n;
if(n<=8)
{
cout<<'0'<
第二題 Self-numbers 2
這道題蠻好的。。 一開始忽略了內存大小，在用哈希表做（把所有不符合的存入哈希表中），在第5組的時候出現了PE。。 PE。。 然後各種調試都PE。。 搜題解， 發現原來這題的位置不是從小到大的，而且可能有重復的位置，那就sort2遍好了。。 第5組爆內存。。 哈希值得問題吧。。 第6組超時。。
然後就知道了，這道題用哈希很膨脹。。
於是 看題解， 他們把這個方式叫做滾動數組。。 說白了，就是數組的重復使用，機智。
他們是這麼做的：1。比如，當前的數字是 13 ，那麼13 可以推出 13+1+3=17 不是，於是 我們知道了 13 後面的第 4 個數字不可取；
2。當前數子是999 那麼就是他後面的 第 27 個數字不可取。
3。最大的數字是10的7次， 那麼他的影響力最多是 7*9=63。 7是位數，9是每位的最大數。於是就可以開一個長度為 126 的數組，以 63 為更新節（最大影響力是63），滾來滾去（f1記錄在63中的（我的這一波），f2記錄我這一波（f1）對下一波的影響力）；
這樣既省內存又方便。。機智。。
#include
#include
#include
#include
#include
using namespace std;
struct shu
{
int v;
int loc;
}who[5001];
int ans[5001];
bool f1[63],f2[63];
int cmp(shu a,shu b)
{
return a.v
第三題 Boxes
這道題一開始很自信，認為自己可以o（1）解決，失敗了。。
但是，再想想一定可以o（1）解決的。。
這裡給出模擬做法，因為有 *2 這個東西，而且數據最大才2的31次，最差的情況就是 31*31 因為每次移動31，運行了31組（log2 2的31次）。。（當然，這不是最差的，因為兩者一定會逐漸接近）但是 900 這樣的時間夠了。。 實驗證明50都可以。。數據水。。
#include
#include
using namespace std;
int main()
{
int a,b;
cin>>a>>b;
int step=0;
int flag=1;
while(a&&b)
{
if(a50)//數據水。。。
{
flag=0;
break;
}
}
if(!flag)
{
cout<<"-1"<
第四題 Palindrome pairs
這個東西，以我目前的水平，還不能統一字符長度為1的情況。。
記錄一下頭尾的所有就好了。。
#include
#include
#include
using namespace std;
char a[2001];
int p[2001];
int q[2001];
int main()
{
scanf("%s",a);
int len=strlen(a);
for(int i=0;i=0&&a[id-to]==a[id+to])
{
p[id-to]++;
q[id+to]++;
to++;
}
id=i;
to=0;
while(id-to-1>=0&&id+to
E 模擬大法好。。 先找到最近的一段，然後就可以玩了。。
#include
#include
#include
#include
using namespace std;
string test;
int main()
{
int n,k;
cin>>n>>k;
cin>>test;
int mode;//不同模式，不同標准。。
if(k==n)
{
mode=1;
}
else if(k==1)
{
mode=2;
}
else if(k>n/2)
{
while(k!=n)
{
cout<<"RIGHT"<=0;i--)
{
cout<<"PRINT "<
F 還是模擬，排序一下就好了。。
#include
#include
#include
using namespace std;
struct sb
{
int x;
int y;
}boom[100010];
int cmp(sb a,sb b)
{
if(abs(a.y)==abs(b.y))
return abs(a.x)0)
{
printf("1 %d R\n",boom[i].x);
mode1=1;
}
else if(boom[i].x<0)
{
printf("1 %d L\n",abs(boom[i].x));
mode1=2;
}
if(boom[i].y>0)
{
printf("1 %d U\n",boom[i].y);
mode2=1;
}
else if(boom[i].y<0)
{
printf("1 %d D\n",abs(boom[i].y));
mode2=2;
}
printf("2\n");
if(mode1==1)
{
printf("1 %d L\n",boom[i].x);
}
else if(mode1==2)
{
printf("1 %d R\n",abs(boom[i].x));
}
if(mode2==1)
{
printf("1 %d D\n",boom[i].y);
}
else if(mode2==2)
{
printf("1 %d U\n",abs(boom[i].y));
}
printf("3\n");
}
return 0;
}
G題 ，這道題 又是模擬，我發現了，在cf裡面即使PE 了都沒問題。。
不過我還是很認真的輸出了。。
這道題運氣好碰巧湊對了。。
值得注意的是下界的計算，反正我因為這個wa2發之後直接偷懶了。。
#include
#include
#include
#include
#include
using namespace std;
struct sb
{
int x;
int y;
char d;
}node[1010];
int wa[2010][1010];
int main()
{
int n;
cin>>n;
int test;
node[0].x=0;
node[0].y=0;
int max1=-0x3f3f3f3f;
int max2=-0x3f3f3f3f;
memset(wa,0,sizeof(wa));
for(int i=1;i<=n;i++)
{
cin>>test;
node[i].x=node[i-1].x+test;
if(i&1)
{
node[i].y=node[i-1].y+test;
}
else
{
node[i].y=node[i-1].y-test;
}
max1=max(max1,node[i].y);
if(node[i-1].y
H Wall Painting
異或 這題不錯,既然要算的是每一個組合後數的和（sum），
1。sum=第一位+第二位+第三位。。。第一位，第二位，第三位。。 他們之間是無關的。
2。這道題算的是所有東西的和，所以重復也沒關系，用不到容斥，話說早上和友人討論的32n微軟面試題 應該容斥做是可行的吧。。（噓）。。
這樣就是一道簡單的排列組合題目了。。
用int wa了。。 那就開 long long 吧
#include
#include
#include
using namespace std;
const long long MOD=1000003;
long long a[10010];
long long wei[64];
long long c[1010][1010];
void build()
{
for(long long i=0;i<=1001;i++)
{
c[i][0]=c[i][i]=1;
for(long long j=1;j>1;
cnt++;
}
maxlen=max(maxlen,cnt);
}
for(long long i=1;i<=n;i++)
{
long long ans=0;
for(long long j=0;j
I Railway Tickets 這道題太有趣了，交了11次。。 因為終點可以在起點前面。。
簡單的dp。。
#include
#include
#include
using namespace std;
int a[10010];
int way[10010];
int main()
{
int l1,l2,l3,c1,c2,c3;
int n;
int s,e;
scanf("%d%d%d%d%d%d",&l1,&l2,&l3,&c1,&c2,&c3);
scanf("%d",&n);
scanf("%d%d",&s,&e);
if(s>e)
swap(s,e);
for(int i=2;i<=n;i++)
{
scanf("%d",&a[i]);
}
memset(way,0x3f3f3f3f,sizeof(way));
way[s]=0;
for(int i=s+1;i<=e;i++)
{
int j=i-1;
int dis=a[i]-a[j];
while(dis<=l1&&j>=s)
{
way[i]=min(way[i],way[j]+c1);
j--;
dis=a[i]-a[j];
}
j=i-1;
dis=a[i]-a[j];
while(dis<=l2&&j>=s)
{
way[i]=min(way[i],way[j]+c2);
j--;
dis=a[i]-a[j];
}
j=i-1;
dis=a[i]-a[j];
while(dis<=l3&&j>=s)
{
way[i]=min(way[i],way[j]+c3);
j--;
dis=a[i]-a[j];
}
}
printf("%d\n",way[e]);
return 0;
}
J Ministry 這道題2刷的時候居然爆內存了。。 哇擦，我第一遍做的時候怎麼可以那麼機智，用數字表示如何走。。用字母果斷爆炸了。。
一開始想到了B題的滾動數組，因為走到下一層，上一層就沒用了。
原來這就是dp裡面套dp，先左掃一遍，然後右邊掃一遍。。 因為某個點，到底是從左走還是從右走，一切都是趨向於最小，所以先左先右沒關系。。
#include
#include
#include
using namespace std;
int a[501];
int time[501];
int way[101][501];
int n;
void print(int who,int len)
{
if(len==0)
return ;
else if(way[len][who]==1)
{
print(who,len-1);
printf("%d",who);
if(len==n)
{
printf("\n");
}
else
printf(" ");
}
else if(way[len][who]==2)
{
print(who-1,len);
printf("%d ",who);
}
else
{
print(who+1,len);
printf("%d ",who);
}
}
int main()
{
int m;
scanf("%d%d",&n,&m);
memset(time,0,sizeof(time));
for(int j=1;j<=n;j++)
{
for(int i=1;i<=m;i++)
{
scanf("%d",&a[i]);
}
for(int i=1;i<=m;i++)
{
time[i]=time[i]+a[i];
way[j][i]=1;
}
for(int i=2;i<=m;i++)
{
if(time[i-1]+a[i]=1;i--)
{
if(time[i+1]+a[i]
K 題，，放一放，放一放，找規律，吃不消。。
現在可以了，根據我的手動模擬，首先來看“。。。。”這種情況，很明顯2個點，然後看“。。。。。”這種情況，3個點。
於是 像這種1條的得出規律n/2+if（奇數）則1；
2*1的時候一個點 2*2 的時候1個點 2*3 的時候，我們找到規律，就是可以消去一條邊 邊成1*3的情況。。2*4 的情況我們可以照樣消去3個點。。於是3就是關鍵。。這樣我們就可以盡可能的去消除3 題目也就是水題了。。
#include
#include
using namespace std;
int main()
{
int n,m;
while(scanf("%d%d",&n,&m)==2)
{
if(n>m)
swap(n,m);
if(n==1||n==2) //2可以轉化為1,1的時候沒有符合要求的1*3
printf("%d\n",(m+1)/2);
else//盡量用1*3消除
{
n=n%3;
m=m%3;
if(n
L Gentlemen
身為大紳士的我，自然要華麗的做出啦。。。
感覺自己比網上題解寫的好多了。。不過方法一樣
用一個pre記錄路徑，dp來看有幾條路。。並不用01背包的樣子。。（反而覺得用了看不懂了）
#include
#include
#include
using namespace std;
int a[110];
int dp[1000010];
int pre[1000010];
int ans[110];
int main()
{
int fin;
scanf("%d",&fin);
int n;
scanf("%d",&n);
memset(dp,0,sizeof(dp));
memset(pre,-1,sizeof(pre));
for(int i=1;i<=n;i++)
{
scanf("%d",&a[i]);
}
dp[0]=1;
for(int i=1;i<=n;i++)
{
for(int j=fin;j>=a[i];j--)
{
if(dp[j-a[i]])
{
dp[j]=dp[j]+dp[j-a[i]];
if(pre[j]==-1)
pre[j]=i;
}
}
}
if(dp[fin]>1)
{
printf("-1\n");
}
else if(dp[fin]==0)
{
printf("0\n");
}
else
{
memset(ans,0,sizeof(ans));
int num=n;
while(pre[fin]!=-1)
{
ans[pre[fin]]=1;
fin=fin-a[pre[fin]];
num--;
}
for(int i=1;i<=n;i++)
{
if(!ans[i])
{
num--;
printf("%d",i);
if(!num)
{
printf("\n");
}
else
{
printf(" ");
}
}
}
}
return 0;
}
M Broken line 這道題一開始沒讀清題目意思，覺得是任何圖形（奇形怪狀），用數學的向量做，然後爆炸啊，寫不出來啊，分類太多了。
然後，搜題解，媽呀，人家為何呢麼幾個等號就出來了呢？原來是方形，方形，方形，一下子水了。。。
#include
#include
#include
#include
using namespace std;
struct sb
{
long long x1,y1;
long long x2,y2;
}xian[10010];
struct sb1
{
long long x;
long long y;
}vector1,vector2,vector3;
int main()
{
long long n;
cin>>n;
for(long long i=1;i<=n;i++)
{
cin>>xian[i].x1>>xian[i].y1>>xian[i].x2>>xian[i].y2;
}
long long x,y;
cin>>x>>y;
long long ok=1;
for(long long i=1;i<=n;i++)
{
if((xian[i].x1==xian[i].x2&&x==xian[i].x1&&y>=min(xian[i].y1,xian[i].y2)&&y<=max(xian[i].y2,xian[i].y1))||(xian[i].y1==xian[i].y2&&y==xian[i].y1&&x<=max(xian[i].x2,xian[i].x1)&&x>=min(xian[i].x1,xian[i].x2)))
{
ok=0;
cout<<"BORDER"<
N Beat
數據小的可憐，dfs一下就好了。。
總算最後一題了。。
#include
#include
#include
#include
using namespace std;
int n;
int flag[20];
int way[20][20];
int ans;
void dfs(int who,int num,int old)
{
ans=max(num,ans);
for(int i=0;i=old)
{
flag[i]=1;
dfs(i,num+1,way[who][i]);
flag[i]=0;
}
}
}
int main()
{
while(scanf("%d",&n)!=EOF)
{
for(int i=0;i
